IOI2021 集训队自选题 Gem Island 2
默认读者已经会了 ICPC2018 World Final Gem Island
下文的 \(a_i\) 均表示分裂次数而非宝石个数
考虑期望的线性性，不难发现恰好有 \(k\) 个人的分裂次数大于 \(i\) 时，对答案有 \(\min(k,r)\) 的贡献，即答案为
\[\sum\limits_{i\ge0}\sum\limits_{k\ge0}\binom{n}{k}\left([x^d]\left(\frac{1-x^{i+1}}{1-x}\right)^{n-k}\left(\frac{x^{i+1}}{1-x}\right)^k\right)\min(k,r)\]
首先可以把 \(\frac{1}{1-x}\) 都提出来并拆开 \(\min\) 分为两种情况
考虑求出了 \(i=0\) 时的多项式 \(F(x)\) 答案即为 \([x^d]\frac{\sum_{i\ge0}F(x^{i+1})}{(1-x)^n}\) 求出了 \(F(x)\) 就可以用高维前缀和（狄利克雷前缀和）把每一次的系数贡献到它所有倍数的答案，就求出了分子，由于 \([x^i] (1+x+x^2+\cdots)^n=\binom{n+i-1}{n-1}\) 不难直接求出答案，于是只考虑 \(F(x)\)
\[\begin{aligned} F(x)=&r\sum\limits_{k\ge r}\binom{n}{k}(1-x)^{n-k}x^k+\sum\limits_{k\le r}k\binom{n}{k}(1-x)^{n-k}x^k\\ =&r\left(\sum\limits_{k\ge 0}\binom{n}{k}(1-x)^{n-k}x^k-\sum\limits_{k\le r}\binom{n}{k}(1-x)^{n-k}x^k\right)+nx\sum\limits_{k\le r}\binom{n-1}{k-1}(1-x)^{(n-1)-(k-1)}x^{k-1}\\ =&r-r\sum\limits_{k\le r}\binom{n}{k}(1-x)^{n-k}x^k+nx\sum\limits_{k\le r-1}\binom{n-1}{k}(1-x)^{n-1-k}x^k \end{aligned}\]
不难发现化为了同一种问题，另外，其中常数项 \(r\) 可以直接去掉，因为常数项都是不贡献到答案的，于是答案为
\[-r\sum\limits_{k\le r}\binom{n}{k}(1-x)^{n-k}x^k+nx\sum\limits_{k\le r-1}\binom{n-1}{k}(1-x)^{n-1-k}x^k\tag{1}\label{1}\]
考虑重新定义 \(F(x)=\sum_{k\le r}\binom{n}{k}(1-x)^{n-k}x^k\)，并定义 \(f(x)=\sum_{k\le r}\binom{n}{k}x^k\)
发现
\[\begin{aligned} f^\prime(x)=&\sum\limits_{k\le r}k\binom{n}{k}x^{k-1}\\ =&n\sum\limits_{k\le r}\binom{n-1}{k-1}x^{k-1} \end{aligned}\]
这个形式看起来很能裂项相消，于是有：
\[\begin{aligned} nf(x)-xf^\prime(x)=&n\sum_{k\le r}\binom{n}{k}x^k-n\sum_{k\le r}\binom{n-1}{k-1}x^k\\ =&n\sum_{k\le r}\binom{n-1}{k}x^k\\ =&f^\prime(x)+n\binom{n-1}{r}x^r \end{aligned}\]
得到：
\[(1+x)f^\prime(x)=n\left(f(x)-\binom{n-1}{r}x^r\right)\tag{2}\label{2}\]
将 \(f(x)\) 带回 \(F(x)\)：\(F(x)=(1-x)^nf\left(\frac{x}{1-x}\right)\)
对 \(F(x)\) 求导得：
\[F^\prime(x)=-n(1-x)^{n-1}f\left(\frac{x}{1-x}\right)+(1-x)^{n-2}f^\prime\left(\frac{x}{1-x}\right)\]
考虑到 \(1+\frac{x}{1-x}=\frac{1}{1-x}\) 带入 \(\eqref{2}\) 式：
\[\frac{1}{1-x}f^\prime\left(\frac{x}{1-x}\right)=n\left(f\left(\frac{x}{1-x}\right)-\binom{n-1}{r}\left(\frac{x}{1-x}\right)^r\right)\]
乘上 \((1-x)^{n-1}\) 得到：
\[(1-x)^{n-2}f^\prime\left(\frac{x}{1-x}\right)=n(1-x)^{n-1}\left(f\left(\frac{x}{1-x}\right)-\binom{n-1}{r}\left(\frac{x}{1-x}\right)^r\right)\]
再带回原式我们得到了 \(F^\prime(x)=-n\binom{n-1}{r}x^r(1-x)^{n-r-1}\)
最后再积分即可，注意这么做之后常数项会丢失，观察 \(\eqref{1}\) 式发现，对于前面一部分，常数项不会贡献到答案，但后一部分因为乘上了 \(nx\) 会贡献到答案到一次项，通过手算发现一次项系数为 \(n\)，直接手动加上即可
时间复杂度 \(\Theta(n\log\log n)\)