CF961G Solution
这题好神啊 … 我发现我一直 WA5 的原因是开始统计和的时候没有取模（
然后就想着写篇题解记录一下 …
首先题目不是要求一个和吗。
那么通过人类智慧发现很显然所有数出现的次数都是一样的。
也就是说最后的和式必然是 $…\times \sum\limits_{i=1}^nw_i$ 这样的形式。
那么不妨将前面的系数设为 $p$。
我们对于这个问题其实可以用 DP 的思想来解决。
我们对于求整个柿子的系数，直接考虑枚举子集大小。
然后就可以发现我们当前选了 $i$ 个，然后算出自己集合的方案和别的集合的方案即可。
最后相乘累加就是答案，其中运用的是第二类斯特林数的思想。
第二类斯特林数就解决的是这样一类问题：
- $n$ 个物品放入 $m$ 个不同集合中，求集合非空的总方案数。
想要研究的同学可以自行研究，这里不再赘述。
所以就可以得到系数 $p$ 变成了下面的柿子。
$$p=\sum\limits_{i=1}^ni\binom{n-1}{i-1}S_2(n-i,k-1)$$
$$=\sum\limits_{i=1}^ni\binom{n-1}{i-1}\dfrac{1}{(k-1)!}\sum\limits_{j=0}^{k-1}(-1)^j\binom{k-1}{j}(k-j-1)^{n-i}$$
$$=\sum\limits_{i=1}^ni\binom{n-1}{i-1}\dfrac{1}{(k-1)!}\sum\limits_{j=0}^{k-1}(-1)^j\dfrac{(k-1)!}{j!\times(k-j-1)!}(k-j-1)^{n-i}$$
$$=\sum\limits_{i=1}^ni\binom{n-1}{i-1}\sum\limits_{j=0}^{k-1}\dfrac{(-1)^j(k-j-1)^{n-i}}{j!\times(k-j-1)!}$$
$$=\sum\limits_{j=0}^{k-1}\dfrac{(-1)^j}{j!\times(k-j-1)!}\sum\limits_{i=1}^ni\binom{n-1}{i-1}(k-j-1)^{n-i}$$
注意上面将 $j$ 的和式提前了，这显然是正确的。
因为分母相同相加分母不变，然后 $-1$ 的系数显然只和 $j$ 有关。
但是分子剩下的部分 $(k-j-1)^{n-i}$ 显然和 $i$ 和 $j$ 都有关。
所以为了方便后面的推导，这里直接将 $j$ 提前作为后面那一堆和的系数。
这里说的 方便推导 其实也没有什么非常清晰的界定，只是这部分可以简单解决。
当然不排除有暴力老哥直接卷的情况。（
其实我也不知道可不可以卷，因为我没学多项式（（
所以看到一大堆阶乘，在保证答案正确性的情况下，直接从一大堆柿子里面拎出来是必要的。
然后后面那个 $(k-j-1)$ 看起来特别丑，弄成 $s$。
$$\sum\limits_{i=1}^ni\binom{n-1}{i-1}s^{n-i}$$
$$=\sum\limits_{i=1}^ni\times s^{n-i}\dfrac{(n-1)!}{(i-1)! \times (n-i)!}$$
为了约分上面的组合数拆开了。
然后有一个 trick，
看到分母有一个 $i-1$，看到前面的系数 $i$，
所以把那个 $i$ 给拆掉，拆成 $i=i-1+1$。
所以有
$$=\sum\limits_{i=1}^ns^{n-i}\times(i-1+1)\dfrac{(n-1)!}{(i-1)! \times (n-i)!}$$
$$=\sum\limits_{i=1}^ns^{n-i}[(i-1)\times \dfrac{(n-1)!}{(i-1)! \times (n-i)!}+\dfrac{(n-1)!}{(i-1)! \times (n-i)!}]$$
$$=\sum\limits_{i=1}^ns^{n-i}(i-1)\dfrac{(n-1)!}{(i-1)! \times (n-i)!}+\sum\limits_{i=1}^ns^{n-i}\dfrac{(n-1)!}{(i-1)! \times (n-i)!}$$
然后约掉共同的 $i-1$。
$$=\sum\limits_{i=1}^ns^{n-i}\dfrac{(n-1)!}{(i-2)! \times (n-i)!}+\sum\limits_{i=1}^n\dfrac{(n-1)!}{(i-1)! \times (n-i)!}$$
再重新写成方便的组合数形式。
$$=\sum\limits_{i=1}^ns^{n-i}\binom{n-1}{i-2}+\sum_{i=1}^ns^{n-i}\binom{n-1}{i-1}$$
由于这个上下不统一所以把 $(n-1)$ 提出来。
$$=(n-1)\sum\limits_{i=1}^ns^{n-i}\binom{n-2}{i-2}+\sum\limits_{i=1}^ns^{n-i}\binom{n-1}{i-1}$$
然后发现这个玩意儿好像很不好算，
所以变成下面这样，因为 $\binom{n}{m}=\binom{n}{n-m}$。
$$=(n-1)\sum\limits_{i=1}^ns^{n-i}\binom{n-2}{n-i}+\sum\limits_{i=1}^ns^{n-i}\binom{n-1}{n-i}$$
然后根据那个什么柿子的展开，就是杨辉三角的系数，
观察到 $n-i$ 的共同部分可以运用上这个公式，
可以发现这个可以直接把组合数拆开变成幂。
实际上那个 $\sum\limits_{i=1}^n$ 有一些项应该是不能算的，因为组合数其实等于 $0$。
所以根据 $(a+b)^n$ 的系数其实就是组合数，可以直接代进去。
即 $(a+b)^n=\sum\limits_{i=0}^n\binom{n}{i}a^{n-i}b^i$。
应该长成这样吧，不太确定有没有问题。
所以又可以化简成下面那样。
$$=(n-1)(s+1)^{n-2}+(s+1)^{n-1}$$
$$=(s+1)^{n-2}(s+1+n-1)$$
$$=(s+1)^{n-2}(s+n)$$
然后就可以代回去了。
$$p=\sum\limits_{j=0}^{k-1}\dfrac{(-1)^j}{j!\times(k-j-1)!}[(n-1)(k-j)^{n-2}+(k-j)^{n-1}]$$
$$=\sum\limits_{j=0}^{k-1}\dfrac{(-1)^j}{j!\times(k-j-1)!}(k-j)^{n-2}(n+k-j-1)$$
所以就可以得出代码了。
我的时间复杂度比较劣，代码还是参考别人的吧。
时间复杂度 $\Theta(k \log \text{Mod})$。
不要问我为什么后面是 $\text{Mod}$ 而不是 $n$（
问就是逆元没有线性求，直接 qpow(x,mod-2)（（（
1 |
|
