Description
一个带标号的图的价值定义为每个点度数的 (k) 次方的和。给定 (n) 和 (k) ，请计算所有 (n) 个点的带标号的简单无向图的价值之和。对 (998244353) 取模。
(1leq nleq 10^9,1leq kleq 200000)
Solution
单独考虑每个点连边情况，容易发现答案就是
[ncdot 2^{n-1choose 2}sum_{i=0}^{n-1}{n-1choose i}i^k]
其中 (i) 枚举的是某一个点的度数， (2^{n-1choose 2}) 为其它的 (n-1) 个点构成的简单无向图个数。
考虑如何求
[sum_{i=0}^{n-1}{n-1choose i}i^k]
注意到第二类斯特林数有这样的一个性质：
[n^k=sum_{i=0}^nS(k,i){nchoose i}i!]
可以用含义证明。
左式能够表示 (k) 个有区别的球放在 (n) 个有区别的盒子中的方案数。
右边则表示先从 (n) 个盒子内选出 (i) 个放球的盒子。再用斯特林数求出放球的方案后乘上 (i!) 表示有序。
带回原式
[egin{aligned}&sum_{i=0}^{n-1}{n-1choose i}sum_{j=0}^iS(k,j){ichoose j}j!\=&sum_{j=0}^{n-1}S(k,j)(j!)sum_{i=j}^{n-1}{n-1choose i}{ichoose j}end{aligned}]
容易发现
[sum_{i=j}^{n-1}{n-1choose i}{ichoose j}]
的含义就是先在 (n-1) 个球中选出 (i) 个，再在 (i) 个球中选出 (j) 个。
我们用含义相同的式子来代替它：
[sum_{i=j}^{n-1}{n-1choose i}{ichoose j}={n-1choose j}cdot 2^{n-1-j}]
那么
[sum_{j=0}^{n-1}(j!){n-1choose j}2^{n-1-j}cdot S(k,j)]
那么不妨用 ( ext{NTT}) 求出 (S(k,j),jin[0,n)) ，并预处理出其它东西就可以直接算了。
值得注意的是由于 (ngg k) 但不过 (S(k,j)=0,k<j) 。所以斯特林数只要处理到 (k) 就好了。
Code
#include <bits/stdc++.h>
using namespace std;
const int N = 200000*4, yzh = 998244353;
int fac[N+5], ifac[N+5], C[N+5];
int n, k;
int a[N+5], b[N+5], R[N+5], len, L;
int quick_pow(int a, int b) {
int ans = 1;
while (b) {
if (b&1) ans = 1ll*ans*a%yzh;
b >>= 1, a = 1ll*a*a%yzh;
}
return ans;
}
void NTT(int *A, int o) {
for (int i = 0; i < len; i++) if (i < R[i]) swap(A[i], A[R[i]]);
for (int i = 1; i < len; i <<= 1) {
int gn = quick_pow(3, (yzh-1)/(i<<1)), x, y;
if (o == -1) gn = quick_pow(gn, yzh-2);
for (int j = 0; j < len; j += (i<<1)) {
int g = 1;
for (int k = 0; k < i; k++, g = 1ll*g*gn%yzh) {
x = A[j+k], y = 1ll*g*A[j+k+i]%yzh;
A[j+k] = (x+y)%yzh, A[j+k+i] = (x-y)%yzh;
}
}
}
if (o == -1)
for (int i = 0, inv = quick_pow(len, yzh-2); i < len; i++) A[i] = 1ll*A[i]*inv%yzh;
}
void work() {
scanf("%d%d", &n, &k); fac[0] = ifac[0] = ifac[1] = C[0] = 1;
for (int i = 2; i <= k; i++) ifac[i] = -1ll*yzh/i*ifac[yzh%i]%yzh;
for (int i = 1; i <= k; i++) C[i] = 1ll*C[i-1]*ifac[i]%yzh*(n-i)%yzh;
for (int i = 1; i <= k; i++)
fac[i] = 1ll*i*fac[i-1]%yzh, ifac[i] = 1ll*ifac[i]*ifac[i-1]%yzh;
for (int i = 0; i <= k; i++) if (i&1) a[i] = -ifac[i]; else a[i] = ifac[i];
for (int i = 0; i <= k; i++) b[i] = 1ll*quick_pow(i, k)*ifac[i]%yzh;
for (len = 1; len <= (k<<1); len <<= 1) ++L;
for (int i = 0; i < len; i++) R[i] = (R[i>>1]>>1)|((i&1)<<(L-1));
NTT(a, 1), NTT(b, 1);
for (int i = 0; i < len; i++) a[i] = 1ll*a[i]*b[i]%yzh;
NTT(a, -1);
int ans = 0;
for (int i = 0; i <= min(n-1, k); i++)
(ans += 1ll*a[i]*fac[i]%yzh*quick_pow(2, n-1-i)%yzh*C[i]%yzh) %= yzh;
ans = 1ll*ans*n%yzh*quick_pow(2, 1ll*(n-1)*(n-2)/2%(yzh-1))%yzh;
printf("%d
", (ans+yzh)%yzh);
}
int main() {work(); return 0; }