BZOJ5093 图的价值 NTT+第二类斯特林数

发布于 2018-02-24  5.24k 次阅读


题意:一个带标号的图的价值定义为每个点度数的k次方的和,给定n(<=1e9)和k(<=2e5),计算所有n个点的带标号的简单无向图的价值之和。

首先写出答案的原始式子:$$ans=n \sum _{d=0}^{n-1}C_{n-1}^{d}d^k * 2^{C_{n-1}^{2}}$$

图不要求连通,也就是边随便连,那么每个点都是等价的,也就是可以直接乘n代表枚举每个点。枚举当前点的度数,那么当前点可以选择一些点连边,乘一下组合数。对于当前点以外的n-1个点,它们之间可以随便连边,那么这个式子就可以理解过去了。

开始化简这个式子,首先要用到斯特林数的性质。

斯特林数的展开形式:$$S(n,k)= \frac {1}{k!} \sum_{i=0}^{k}C_{k}^{i}(-1)^{i}(k-i)^n$$

然后变形成这个式子:$$k^n=\sum_{i=0}^{n} S(n,i) C(k,i) i!$$

如果从实际角度理解,第二类斯特林数是n个球放进了k个无标号的盒子的方案数,那么等式左边就是n个球放进了k个有标号的盒子,右边就是枚举非0盒子的个数。当然,如果使用二项式反演也是可以证明的。放个链接:

第 二 类 斯 特 林 数 小 结

然后为了方便,给n减1,把上面的式子带进去:

$$ans=(n+1)2^{C_{n}^{2}} \sum _{i=0}^{n} C_{n}^{i} \sum_{j=0}^{i}S_{k,j}C_{i}^{j}j!$$

交换ij,发现要解决$$\sum_{i=j}^{n}C_{n}^{i}C_{i}^{j}$$,问题就简单了,因为斯特林数在n<k时为0,所以枚举的上限变成了min(n,k)。

还是从组合意义上想,上面的式子等效于在一个长为n的序列上把任意格子涂黄,同时允许给j个黄格子涂红,求不同的方案数。显然等效于选j个格子涂橙色,其他的格子涂黄色,因此等于$$C_{n}^{j}2^{n-j}$$

代进入就是最后的答案:$$ans=(n+1)2^{C_{n}^{2}}\sum_{j=0}^{min(n,k)}S(k,j)j!C_{n}^{j}2^{n-j}$$

最后要做的其实就是NTT预处理一行斯特林数了。

$$S_{n,k}=\sum_{i=0}^{k}\frac{(-1)^i}{i!}*\frac{(k-i)^n}{(k-i)!}$$

然后这道题就做完了,感觉推理过程中用到的两个式子都不太好推,这道题的难度也就一下子高了很多。

 


Narcissus | HZOIer | zhuohaoyu1228@gmail.com | QQ 943382974