【重度魔怔】CF 2030E 题解

· · 题解

由于下午 ucup K 题柿子推得过于热火朝天了，我们再次考虑推柿子。

还是考虑算贡献，容易发现大小为 v 的数中，被选上 的第 i 个数对答案有 1 的贡献当且仅当 [0, v) 中每个数都被选了至少 i 个。到这里可以直接 DP，但是我们坚持推柿子！！！

记 tot 为 \ge v 的数的个数，c_i 为大小为 i 的数的个数。不难发现，大小为 v 的数的总贡献为：

\text{Ans} = \sum_{i=0}^{c_v-1}2^{tot-i-1}\sum_{j=0}^{i}\binom{i}{j}\prod_{k=0}^{v-1}\sum_{o=j+1}^{v_k}\binom{c_k}{o}

看起来很吓人对不对，但是冷静分析一下：

\text{Ans}=2^{tot-1}\sum_{j=0}^{c_v-1}\red{\sum_{i=0}^{c_v-1}(\frac{1}{2})^{i}\binom{i}{j-1}}\cdot\blue{\prod_{k=0}^{v-1}\sum_{o=j}^{v_k}\binom{c_k}{o}}

蓝色部分可以每次预处理，所以我们只要能在一个合理的时间内，对于一个 j 算出红色部分就做完了！！！

相当于有 f(n,m)=\sum_{i=0}^{n-1}z^i\binom{i}{m}，其中 z 是一个不为 1 的常数，我们需要求出某一行（即：n 均相同）的值。

还是考虑拆组合数：

\begin{aligned} f(n,m)&=\sum_{i=0}^{n-1}z^i[x^m](x+1)^i \\ &= [x^m]\sum_{i=0}^{n-1}z^i(x+1)^i \\ &= [x^m]\frac{1-(z(x+1))^n}{1-z(x+1)} \end{aligned}

多项式求逆即可 O(m \log m) 求一行。

代码可以见这里。

cxy 说可以找整式递推做到线性，先咕了。

upd: 会了。

不用啥高深的科技，我们直接考虑拆组合数。

\begin{aligned} f(n,m)&=\sum_{i=0}^{n-1}z^i\binom{i}{m} \\ &= \sum_{i=0}^{n-1}z^i(\binom{i-1}{m-1}+\binom{i-1}{m}) \\ &= (z\sum_{i=0}^{n-1}z^i\binom{i}{m-1})+(z\sum_{i=0}^{n-1}z^i\binom{i}{m})-z^n(\binom{n-1}{m}+\binom{n-1}{m-1}) \\ &= z\cdot f(n, m-1)+z\cdot f(n,m)-z^n(\binom{n-1}{m}+\binom{n-1}{m-1}) \end{aligned}

又因为 z\neq 1，故有

f(n,m)=\frac{z\cdot f(n,m-1)-z^n(\binom{n-1}{m}+\binom{n-1}{m-1})}{1-z}