一道有趣的幼儿园组合题的许许多多解法

题面 > 有 $n$ 个⿊球，$m$ 个⽩球，每次等概率取出⼀个球(不放回)，将取出来的球的颜⾊写成⼀个 $01$ 序列，求 `01` 的期望出现次数。所有运算均在 $\bmod 998244353$ 意义下进行。 > > | 子任务编号 | 分值 |$\max\{n,m\}$ | 特殊性质 | |:-----: | :----------: | :----------: |:---:| |$\rm Subtask1$ | $5$ | $\leqslant 20$ | \ | |$\rm Subtask2$ | $30$ | $\leqslant 300$ | \| |$\rm Subtask3$ | $25$ | $\leqslant 5000$ | \| |$\rm Subtask4$ | $10$ | $\leqslant 5\cdot 10^6$ | $n=m$| |$\rm Subtask5$ | $15$ | $\leqslant 10^6$ | \ | |$\rm Subtask5$ | $15$ | $\leqslant 10^{9}$ | \ | _____ # 5pts 做法 枚举所有可能的颜色排列，复杂度 $O(n\cdot 2^n)$。 # 35pts 做法 设 $X$ 表示出现次数，那么有 $$ \mathbb{E}(X)=\sum_{i=1}^{\min\{n,m\}}\Pr(X=i)\cdot i $$ 考虑这个 $X=i$ 怎么算，本质上是求 $01$ 排列有多少种方案存在恰好 $i$ 个 `01`，也就只需要计算 $i$ 个相隔距离 $\geq 1$ 的 $0$ 的方案数。这个地方想了一会儿没找到什么闭形式，于是打算直接 $dp$ 。 设 $f_{i,j,k,0/1}$ 表示前 $i$ 位有 $j$ 个 $0$ ，其中有 $k$ 个 $01$ ，且第 $i$ 位放了 $0/1$ 的方案数，那么有转移 $$ f_{i+1,j,k+1,1}\leftarrow f_{i,j,k,0}\to f_{i+1,j+1,k,0} $$ $$ f_{i+1,j+1,k,0}\leftarrow f_{i,j,k,1}\to f_{i+1,j,k,1} $$ 时空复杂度均为 $O(n^3)$ 。 # 60pts 做法 发现继续沿用对着每个 $i$ 求贡献的做法。发现本质上就是从长为 $n+m$ 的序列里面选出 $i$ 个不相邻的 `0` 的方案数。考虑转化一下这个问题。首先可以转化成从 $1\sim n +m$ 里面选择 $i$ 个不相邻的数的方案数。之后考虑对于选出来的数 $a_1,a_2,a_3\cdots a_i$ ，从小到大排序后一定满足 $$ a_1<a_2-1<a_3-1<a_4-1< \cdots<a_{i}-1 $$ 考虑令 $$ b_1=a_1-1,b_2=a_2-2,b_3=a_3-3,b_4=a_4-4\cdots b_i=a_i-i $$ 发现这样随便选择两个相邻的 $b_{k},b_{k+1}$ 都会有 $$ b_k=a_k-k<a_{k+1}-1-k=a_{k+1}-{k+1}=b_{k+1} $$ 也就是从 $1\sim n+m-i$ 中选择可以相邻的 $\{b\}$ 的方案数等于在 $1\sim n+m$ 中选择不能相邻的 $\{a\}$ 的方案数。于是可以知道有 $i$ 个 $01$ 时的方案数就是 $$ f_i=\binom{n+m-i}{i}\cdot \binom{n+m-2\cdot i}{n-i} $$ 注意到因为序列其他位置的方案数也要考虑，所以需要再乘上一个剩下未知的方案数。但是注意到，剩下位置可能还会存在 $01$ ，所以 $f_i$ 本质上算的是「至少 $i$ 个的方案数」。设 $g_i$ 表示「恰好 $i$ 个的方案数」，那么可知： $$ g_i=\sum_{j\geq i} \binom{j}{i} \cdot (-1)^{j-i}f_j $$ 因为有二项式反演： $$ f(n)=\sum_{i=n}^{m}\left(\begin{array}{c}i \\ n\end{array}\right) g(i) \Leftrightarrow g(n)=\sum_{i=n}^{m}(-1)^{i-n}\left(\begin{array}{c}i \\ n\end{array}\right) f(i) $$ 然后就可以获得一个时空复杂度均为 $O(n^2)$ 的做法。 # 70pts 做法 有特殊性质 $n=m$。可以通过进一步对上一个做法用组合恒等式来化简，或者直接找规律，可以发现当 $n=m$ 时，$g_i=\binom{n}{i}^2$。于是就可以线性做了。 # 85pts 做法 并不会，有人来教教我吗？不过似乎二项式反演那部分是可以做到 $\log^2$ 的？这可能需要什么多项式科技。 # 100pts 做法 发现对于期望，只需要算出所有情况下 $01$ 数量的总和，除以全部的合法排列数即可。考虑这个总和也是可以分开算的，即可以算对于每个可能出现的 `01` 计算与之对应的有多少贡献。于是答案就是：于是答案就是： $$ \frac{(n+m-1)\cdot \binom{n+m-2}{m-1}}{\binom{n+m}{m}} $$ 化简一下可以得到答案为 $$ \frac{n\times m}{n+m} $$ 复杂度 $O(\log n)$ 。 # 声明 题目以及以上题解版权归 @皎月半洒花 所有 ~~因为我可能什么时候就拿这题去骗钱了。~~