题解：P15211 [NWERC 2025] Erratic Lights

· · 题解

link

Solution

考虑三个颜色的灯泡的数量排序后为 a,b,c，其中 a \le b \le c，数量为 a,b,c 的灯泡我们称为 A,B,C。

我们可以对 A 进行修改，把 A 全部变为 B 或 C，期望次数为 \dfrac{3}{2} \times a。

假设变完后加了 i 个 B，概率为 \dfrac{\dbinom{a}{i}}{2^a}。

在这之后，我们可以把 B 变为 C 或把 C 变为 B，这一部分期望次数为：

\dfrac{1}{2^a} \times \sum\limits_{i=0}^{a} {3 \times \dbinom{a}{i} \times \min({b+i,c+(a-i)})}

，所以总期望次数为：

\dfrac{3}{2} \times a + \dfrac{1}{2^a} \times \sum\limits_{i=0}^{a} {3 \times \dbinom{a}{i} \times \min({b+i})}

，我怕组合数的计算过程中会爆 __int128，所以我用了 python。

Code

:::success[code]

n=int(input())
s=input()
def A(x,y):
    c=1
    for i in range(y-x+1,y+1):
        c*=i
    return c;
def C(x,y):
    if x==0:
        return 1
    else:
        return A(x,y)//A(x,x)
r=0
g=0
cntb=0
for i in range(n):
    if s[i]=='r':
        r+=1
    elif s[i]=='g':
        g+=1
    else:
        cntb+=1
ans=0
a,b,c=min([r,g,cntb]),r+g+cntb-min([r,g,cntb])-max([r,g,cntb]),max([r,g,cntb])
for i in range(a+1):
    d=C(i,a)*3*min([b+i,c+(a-i)])
    ans+=d;
ans/=(1<<a)
ans+=a*1.5
print(ans)

:::