problem
- 定义一个点的权值为它的度数的 \(m\) 次方，规定 \(0^0=1\)。
- 对于一张无向图，它的权值是所有点的权值和。
- 求所有 \(n\) 个点的无向图（共有 \(2^{C_n^2}\) 种）的权值之和，对 \(998244353\) 取模。
- \(1≤n≤10^9,0≤m≤5*10^5\)
Solution
- 分别考虑每个点对答案的贡献：固定一个点 \(u\)，枚举 \(u\) 的度数 \(i\)，对答案的贡献为 \(i^m\)。而满足 \(u\) 度数为 \(i\) 的图中，另外 \(n-1\) 个点要选出 \(i\) 个点跟 \(u\) 连边（方案数：\(C_{n-1}^i\)）。然后另外 \(n-1\) 个点两两之间可以随意连边（方案数：\(2^{C_{n-1}^2}\)）。而 \(u\) 可以是 \(1\) ~ \(n\) 的任意一个点，所以有：
\[ans=n*2^{C_{n-1}^2}*\sum_{i=0}^{n-1}i^m*C_{n-1}^i
\]
- 显然我们只要求：
\[sum=\sum_{i=0}^{n-1}i^m*C_{n-1}^i
\]
- 众所周知：
\[i^m=\sum_{j=0}^{m}S(m,j)*C_i^j*j!
\]
- 那么有：
\[sum=\sum_{j=0}^{m}S(m,j)*j!*\sum_{i=0}^{n-1}C_i^j*C_{n-1}^i
\]
- 考虑 \(C_i^j*C_{n-1}^i\) 的组合意义：\(n-1\) 个带编号的球里面选出 \(i\) 个涂成蓝色，再在这 \(i\) 个里面选出 \(j\) 个涂成红色。这等价于：\(n-1\) 个带编号的球里面选出 \(j\) 个涂成红色，再在剩下的 \(n-j-1\) 个里面选出 \(i-j\) 个涂成蓝色。
- 那么有：
\[sum=\sum_{j=0}^{m}S(m,j)*j!*C_{n-1}^j*\sum_{i=0}^{n-1}C_{n-j-1}^{i-j}
\]
- 即：
\[sum=\sum_{j=0}^{m}S(m,j)*j!*C_{n-1}^j*2^{n-j-1}
\]
- 众所周知：
\[S(m,j)=\frac{1}{j!}\sum_{i=0}^{j}(-1)^i*(j-i)^n*C_j^i
\]
- 那么我们可以用 \(NTT\) 求出每个 \(S(m,j)\)，时间复杂度 \(O(m \log m)\)。
Code
#include <bits/stdc++.h>
using namespace std;
#define ll long long
template <class t>
inline void read(t & res)
{
char ch;
while (ch = getchar(), !isdigit(ch));
res = ch ^ 48;
while (ch = getchar(), isdigit(ch))
res = res * 10 + (ch ^ 48);
}
const int mod = 998244353, e = 2e6 + 5;
int n, m, lim, rev[e], g[e], h[e], f[e], fac[e], inv[e], ans;
inline int ksm(int x, ll y)
{
int res = 1;
while (y)
{
if (y & 1) res = (ll)res * x % mod;
y >>= 1;
x = (ll)x * x % mod;
}
return res;
}
inline void upt(int &x, int y)
{
x = y;
if (x >= mod) x -= mod;
}
inline void fft(int n, int *a, int op)
{
int i, j, k, r = (op == 1 ? 3 : (mod + 1) / 3);
for (i = 0; i < n; i++)
if (i < rev[i]) swap(a[i], a[rev[i]]);
for (k = 1; k < n; k <<= 1)
{
int w0 = ksm(r, (mod - 1) / (k << 1));
for (i = 0; i < n; i += (k << 1))
{
int w = 1;
for (j = 0; j < k; j++)
{
int b = a[i + j], c = (ll)w * a[i + j + k] % mod;
upt(a[i + j], b + c);
upt(a[i + j + k], b + mod - c);
w = (ll)w * w0 % mod;
}
}
}
}
int main()
{
freopen("graph.in", "r", stdin);
freopen("graph.out", "w", stdout);
cin >> n >> m;
lim = 1;
int i, k = 0;
while (lim < m * 2 + 5)
{
lim <<= 1;
k++;
}
fac[0] = 1;
for (i = 1; i <= m; i++) fac[i] = (ll)fac[i - 1] * i % mod;
inv[m] = ksm(fac[m], mod - 2);
for (i = m - 1; i >= 0; i--) inv[i] = (ll)inv[i + 1] * (i + 1) % mod;
for (i = 0; i < lim; i++) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << k - 1);
for (i = 0; i <= m; i++)
{
if (i & 1) g[i] = mod - 1;
else g[i] = 1;
g[i] = (ll)g[i] * inv[i] % mod;
h[i] = (ll)inv[i] * ksm(i, m) % mod;
}
fft(lim, g, 1);
fft(lim, h, 1);
for (i = 0; i < lim; i++) f[i] = (ll)g[i] * h[i] % mod;
fft(lim, f, -1);
int tot = ksm(lim, mod - 2);
for (i = 0; i < lim; i++) f[i] = (ll)f[i] * tot % mod;
int c = 1;
for (i = 0; i <= m; i++)
if (n - 1 >= i)
{
ans = (ans + (ll)f[i] * fac[i] % mod * c % mod * ksm(2, n - 1 - i)) % mod;
c = (ll)c * ksm(i + 1, mod - 2) % mod * (ll)(n - 1 - i) % mod;
}
else break;
ans = (ll)ans * n % mod * ksm(2, (ll)(n - 1) * (n - 2) / 2) % mod;
cout << ans << endl;
return 0;
}