本文共 2338 字,大约阅读时间需要 7 分钟。
Description
“简单无向图”是指无重边、无自环的无向图(不一定连通)。 一个带标号的图的价值定义为每个点度数的k次方的和。
给定n和k,请计算所有n个点的带标号的简单无向图的价值之和。 因为答案很大,请对998244353取模输出。
Input
第一行包含两个正整数n,k(1<=n<=10^9,1<=k<=200000)。
Output
输出一行一个整数,即答案对998244353取模的结果。
Sample Input
6 5
Sample Output
67584000
题解
一般都要单独考虑一个点的贡献
显然这个点的贡献是独立的,最后乘一个n就可以 那单独一个点的贡献就是 ∑ i = 1 n − 1 C n − 1 i ∗ 2 ( n − 1 ) ( n − 2 ) 2 ∗ i k \sum_{i=1}^{n-1}C_{n-1}^i*2^{\frac{(n-1)(n-2)}{2}}*i^k i=1∑n−1Cn−1i∗22(n−1)(n−2)∗ik 2的次幂是常数,提到前面去,把n减一,显然我们只需要算 ∑ i = 1 n C n i ∗ i k \sum_{i=1}^nC_{n}^{i}*i^k i=1∑nCni∗ik 根据第二类斯特林数的性质,我们可以知道 ∑ i = 1 n C n i ∑ j = 0 m i n ( i , k ) S ( k , j ) ∗ j ! ∗ C i j \sum_{i=1}^nC_{n}^{i}\sum_{j=0}^{min(i,k)}S(k,j)*j!*C_{i}^{j} i=1∑nCnij=0∑min(i,k)S(k,j)∗j!∗Cij 乘法分配律一下,显然可以把斯特林数提前 ∑ i = 0 m i n ( n , k ) S ( k , i ) ∗ i ! ∗ ∑ j = i n C n j ∗ C j i \sum_{i=0}^{min(n,k)}S(k,i)*i!*\sum_{j=i}^{n}C_n^j*C_{j}^{i} i=0∑min(n,k)S(k,i)∗i!∗j=i∑nCnj∗Cji 后面的式子的意义就是在n中选i个数,其它可选可不选,所以就是 ∑ i = 0 m i n ( n , k ) S ( k , i ) ∗ i ! ∗ C n i ∗ 2 n − i \sum_{i=0}^{min(n,k)}S(k,i)*i!*C_{n}^{i}*2^{n-i} i=0∑min(n,k)S(k,i)∗i!∗Cni∗2n−i 现在就是要算前面的斯特林数了 可以容斥然后NTT n l o g n nlogn nlogn求,点一下就知道啦
#include#include #include #include #include #include #include #include #include
转载地址:http://immu.baihongyu.com/