题目大意：一个圆上有 $2n$ 颗珠子，每颗珠子为黑色或白色，且每种颜色的数量均为偶数。将所有同色的珠子两两匹配，所得的线段会产生一些交点，仅考虑其中白线和黑线相交的交点。定义 $f$ 所有匹配中异色交点的最小值。现在给出一个长度为 $2n$ 的串 $s$，由 bw? 组成，其中 ? 可以选填 b 或 w。求所有合法方案 $f$ 的期望。另外，还会对 $s$ 有 $m$ 次修改，每次修改一个字符。

题解：虽然说也观察到了性质，但是还是题解的好用啊。

我的性质：可以证明会尽量连接两个相邻的同色珠子，$f$ 等于将所有相邻同色珠子不断删去后剩余珠子数量的 $\frac{1}{4}$。

题解的性质：记 $b_{e},b_{o}$ 分别表示在偶数和奇数位置的黑色珠子数量，$f=\frac{1}{2}|b_{e}-b_{o}|$。

容易看出两个性质等价。

设 $p_{e},p_{o}$ 分别表示在偶数和奇数位置的 ? 个数，$p=p_{e}+p_{o}$。那么答案为

$$ \begin{aligned} &\frac{1}{2^{p}}\sum_{i=-\infty}^{+\infty}[i+b_{e}-b_{o}\equiv 0\pmod 2]|i+b_{e}-b_{o}|\sum_{t=-\infty}^{+\infty}{p_{e}\choose t}{p_{o}\choose t-i}\\ =&\frac{1}{2^{p}}\sum_{i=-\infty}^{+\infty}[i+b_{e}-b_{o}\equiv 0\pmod 2]|i+b_{e}-b_{o}|{p\choose p_{o}+i}\\ =&\frac{1}{2^{p}}\sum_{i=0}^{p}[i+c\equiv 0\pmod 2]|i+c|{p\choose i} \end{aligned} $$

其中 $c=b_{e}-b_{o}-p_{o}$。不考虑 $\frac{1}{2^{p}}$，且省略同余条件。

$$ \begin{aligned} =&\sum_{i=0}^{-c}(-i-c){p\choose i}+\sum_{i=-c+1}^{p}(i+c){p\choose i}\\ =&-\sum_{i=0}^{-c}p{p-1\choose i-1}+c{p\choose i}+\sum_{i=-c+1}^{p}p{p-1\choose i-1}+c{p\choose i}\\ =&-\sum_{i=0}^{-c}p{p-1\choose i-1}+c{p\choose i}+\sum_{j=0}^{p+c-1}p{p-1\choose j}+c{p\choose j} \end{aligned} $$

注意这里 $i$ 和 $j$ 的奇偶性条件是不一样的。

这个时候，我们只需要维护 $S(n,m,k)=\sum_{i=0}^{m}[i\equiv k\pmod{2}]{n\choose i}$，注意到每次修改只会导致 $n,m$ 产生 $O(1)$ 的变化，使用我们熟悉的递推即可求得。

update：事实上

$$ \begin{aligned} &S(n,m,k)\\ =&\sum_{i=0}^{m}[i\equiv k\pmod{2}]{n\choose i}\\ =&\sum_{i=0}^{m-[m\not\equiv k\pmod{2}]}{n-1\choose i} \end{aligned} $$

这样就不需要讨论奇偶，方便多了。