题面
题解
由题面, 我们可以得出这样一个 ** 式子
[displaystyle ans = sum_{forall G}sum_{i=1}^{n}d_i^k
]
其中 (d_i) 代表 (i) 点的度数
这个式子意为, 对于任意的一个简单无向图, 把每个点的答案加上...
这个.... 似乎并不好算, 我们尝试对于某一个点 (i) , 把他在每个图中的贡献放到一起讨论看一看
首先, 度数不同肯定贡献不同, 我们要枚举贡献
那这个贡献会算多少次呢
注意到我们并不需要图联通, 只要没有自环和重边即可
那么对于其他的 (n - 1) 个点, 他们之间可以任意连边
所以我们就将上式转化为
[displaystyle ans = sum_{i=1}^nsum_{d=0}^{n-1}inom{n-1}{d}d^k*2^{frac{(n - 1)(n - 2)}{2}}
]
代表我们对于 (i) 点, 选 (d) 条边连出去, 有 (n - 1) 条边可选, 然后其他的点随便连
接着我们发现每一个点最后的贡献都是相同的, 这个枚举的 (i) 似乎并没有什么用
所以有
[displaystyle ans = n*2^{frac{(n - 1)(n - 2)}{2}}sum_{d=0}^{n-1}inom{n-1}{d}d^k
]
后面这个式子似乎在哪里见过
然后按照上面的推导, 最后化出来是这个样子的
[displaystyle ans = n*2^{frac{(n - 1)(n - 2)}{2}}sum_{i=0}^{k}i!egin{Bmatrix}k\iend{Bmatrix}inom{n-1}{i}2^{n-i}
]
但是这个题中的 (k) 比较大, 这个第二类斯特林数有点难搞
有了!
我们发现第二类斯特林数有这样一个递推式
[displaystyle egin{aligned}egin{Bmatrix}n\mend{Bmatrix}&=frac{1}{m!}sum_{i=0}^{m}(-1)^iinom{m}{i}(m-i)^n\&=frac{1}{m!}sum_{i=0}^m(-1)^ifrac{m!}{i!(m-i)!}(m-i)^n\&=sum_{i=0}^mfrac{(-1)^i}{i!}*frac{(m-i)^n}{(m-i)!}end{aligned}
]
这是个卷积, NTT 求一下就好了
Code
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
const int N = 200005;
const int mod = 998244353;
using namespace std;
int n, m, k, len, lim, r[N << 2], a[N << 2], b[N << 2], g, gg, fac[N], inv[N], ans;
template < typename T >
inline T read()
{
T x = 0, w = 1; char c = getchar();
while(c < '0' || c > '9') { if(c == '-') w = -1; c = getchar(); }
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * w;
}
int fpow(int x, int y)
{
int res = 1;
for( ; y; y >>= 1, x = 1ll * x * x % mod)
if(y & 1) res = 1ll * res * x % mod;
return res;
}
void ntt(int *p, int opt)
{
for(int i = 0; i < k; i++)
if(i < r[i]) swap(p[i], p[r[i]]);
for(int i = 1; i < k; i <<= 1)
{
int rt = fpow(opt == 1 ? g : gg, (mod - 1) / (i << 1));
for(int j = 0; j < k; j += (i << 1))
{
int w = 1;
for(int l = j; l < j + i; l++, w = 1ll * w * rt % mod)
{
int x = p[l], y = 1ll * w * p[l + i] % mod;
p[l] = (x + y) % mod, p[l + i] = (x - y + mod) % mod;
}
}
}
}
void prepare1()
{
g = 3, gg = fpow(g, mod - 2);
for(int i = (fac[0] = 1); i <= k; i++)
fac[i] = 1ll * fac[i - 1] * i % mod;
inv[k] = fpow(fac[k], mod - 2);
for(int i = k - 1; i >= 0; i--)
inv[i] = 1ll * inv[i + 1] * (i + 1) % mod;
}
void prepare2()
{
for(int i = 0; i <= k; i++)
a[i] = 1ll * (i & 1 ? mod - 1 : 1) * inv[i] % mod;
for(int i = 0; i <= k; i++)
b[i] = 1ll * fpow(i, k) * inv[i] % mod;
for(len = 2 * k, k = 1; k <= len; k <<= 1, lim++); lim--;
for(int i = 0; i < k; i++)
r[i] = (r[i >> 1] >> 1) | ((i & 1) << lim);
ntt(a, 1), ntt(b, 1);
for(int i = 0; i < k; i++)
a[i] = 1ll * a[i] * b[i] % mod;
ntt(a, -1);
int tmp = fpow(k, mod - 2);
for(int i = 0; i < k; i++)
a[i] = 1ll * a[i] * tmp % mod;
}
int main()
{
n = read <int> (), k = read <int> (), m = min(n - 1, k);
prepare1(), prepare2();
for(int res = 1, i = 0; i <= m; res = 1ll * res * (n - i - 1) % mod, i++)
ans = (ans + 1ll * res * a[i] % mod * fpow(2, n - i - 1) % mod) % mod;
ans = 1ll * ans * n % mod * fpow(2, 1ll * (n - 1) * (n - 2) / 2 % (mod - 1)) % mod;
printf("%d
", ans);
return 0;
}