BZOJ5093 图的价值 [NTT][斯特林数]

Description

“简单无向图”是指无重边、无自环的无向图（不一定连通）。

一个带标号的图的价值定义为每个点度数的k次方的和。

给定n和k，请计算所有n个点的带标号的简单无向图的价值之和。

因为答案很大，请对998244353取模输出。

Input

第一行包含两个正整数$n,k(1\le n\le 10^9,1\le k\le 200000)$

Output

输出一行一个整数，即答案对998244353取模的结果。

Sample Input

6 5

Sample Output

67584000

算法讨论

首先很容易的出一个$O(n)$ 的式子：

$$ans = n * 2^\binom{n - 1}{2} * \sum_{i =1}^{n - 1}\binom{n-1}{i}*i^k$$

这个式子意义为对每个点计算贡献，枚举它的度数，剩下的点可以随意连

瓶颈在于求$\sum_{i =1}^{n}\binom{n}{i}*i^k$

考虑这个式子的组合意义，现在有$n$个盒子，选出$i$个盒子，将$k$个球按顺序往里放的方案数

用斯特林数转化一下

$$=\sum_{i=1}^n C(n,i) * S(k,i) * 2^{n - i} * n!$$

考虑上面的式子，我们把球往里面放，会出现一些空的盒子

我们现在枚举的$i$个盒子，是都不为空的，而往$i$个盒子里放$k$个数，就是第二类斯特林数$S(k,i)$

由于第二类斯特林数无序，乘上$n!$消序

再乘上$2^{n-i}$对应原来可能为空的方案

考虑斯特林数式子

$$S(n,m) = \frac 1 {m!} \sum_{i=0}^m(-1)^i*\binom m i (m-i)^n$$

就可以卷积求出