对峙绝望
题目链接:YBT2023寒假Day1 C
题目大意
定义一个无向图的权值是所有结点度数的 k 次方之和。(规定 0 的 0 次方是 1)
求所有 n 个点的简单无向图的权值之和。
对 998244353 取模。
思路
首先会发现每个点其实是一样的(除了编号),那我们可以只求出一个的贡献,然后总答案就是一个的 \(*n\)。
然后因为 \(n\) 太大一个 \(d^k\) 下面太大了,我们考虑用第二类斯特林数进行分解:
\(d^k=\sum\limits_{i=0}^kS(k,i)C(d,i)i!\)
(\(d^k\) 相当于 \(k\) 个有标号球放入 \(d\) 个有标号的桶)
(然后 \(S(k,i)\) 是 \(k\) 个有标号球放入 \(i\) 个无标号桶且每个桶非空)
(然后枚举非空桶的数量,然后再 \(C(d,i)\) 看是哪些桶,然后再用 \(i!\) 给选了的桶标号)
那你就变成对于 \(1\sim k\) 的每个 \(i\),你要求所有简单无向图中 \(1\) 号点连的边中选出 \(i\) 条的方案数之和。
考虑反置一下要求,先选出 \(i\) 条边,再看别的边选不选(那这些任选)。
也就是 \(C(n-1,i)2^{n(n-1)/2-i}\)(注意是 \(C(n-1,i)\) 因为跟 \(1\) 号点连边的边数是 \(n-1\))
那我们设这个东西是 \(Sum_i\),那我们要的答案其实就是:
\(\sum\limits_{i=0}^kS(k,i)Sum_ii!\)
那剩下的问题就是如何预处理 \(S(k,i)\),那这是一个经典的第二类斯特林数行的问题,用容斥:
\(m!S(n,m)=\sum\limits_{i=0}^m(-1)^{m-i}C(m,i)i^n\)
拆开组合数:
\(m!S(n,m)=m!\sum\limits_{i=0}^m\dfrac{(-1)^{m-i}}{(m-i)!}\dfrac{i^n}{i!}\)
\(S(n,m)=\sum\limits_{i=0}^m\dfrac{(-1)^{m-i}}{(m-i)!}\dfrac{i^n}{i!}\)
那这个就是一个卷积的形式,直接 NTT 就好了。
代码
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define mo 998244353
#define ll long long
#define clr(f, x) memset(f, 0, sizeof(int) * (x))
#define cpy(f, g, x) memcpy(f, g, sizeof(int) * (x))
using namespace std;
const int N = 5e5 + 100;
const int pN = N * 8;
int n, k, jc[N], inv[N], invs[N], S[N];
int f[pN], g[pN];
int add(int x, int y) {return x + y >= mo ? x + y - mo : x + y;}
int dec(int x, int y) {return x < y ? x - y + mo : x - y;}
int mul(int x, int y) {return 1ll * x * y % mo;}
int ksm(int x, ll y) {
int re = 1;
while (y) {
if (y & 1) re = mul(re, x);
x = mul(x, x); y >>= 1;
}
return re;
}
int C(int n, int m) {
if (n < 0 || m < 0 || n < m) return 0;
return mul(mul(jc[n], invs[m]), invs[n - m]);
}
struct Poly {
int an[pN], G = 3, Gv;
void Init() {
jc[0] = 1; for (int i = 1; i < N; i++) jc[i] = mul(jc[i - 1], i);
inv[0] = inv[1] = 1; for (int i = 2; i < N; i++) inv[i] = mul(inv[mo % i], mo - mo / i);
invs[0] = 1; for (int i = 1; i < N; i++) invs[i] = mul(invs[i - 1], inv[i]);
Gv = ksm(G, mo - 2);
}
void get_an(int limit, int l_size) {
for (int i = 0; i < limit; i++)
an[i] = (an[i >> 1] >> 1) | ((i & 1) << (l_size - 1));
}
void NTT(int *f, int limit, int op) {
for (int i = 0; i < limit; i++)
if (i < an[i]) swap(f[i], f[an[i]]);
for (int mid = 1; mid < limit; mid <<= 1) {
int Wn = ksm(op == 1 ? G : Gv, (mo - 1) / (mid << 1));
for (int j = 0, R = (mid << 1); j < limit; j += R)
for (int w = 1, k = 0; k < mid; k++, w = mul(w, Wn)) {
int x = f[j | k], y = mul(w, f[j | mid | k]);
f[j | k] = add(x, y); f[j | mid | k] = dec(x, y);
}
}
if (op == -1) {
int limv = ksm(limit, mo - 2);
for (int i = 0; i < limit; i++) f[i] = mul(f[i], limv);
}
}
void px(int *f, int *g, int limit) {
for (int i = 0; i < limit; i++)
f[i] = mul(f[i], g[i]);
}
void times(int *f, int *g, int n, int m, int T) {
int limit = 1, l_size = 0; while (limit < n + m) limit <<= 1, l_size++;
get_an(limit, l_size);
static int tmp[pN]; clr(f + n, limit - n); cpy(tmp, g, m); clr(tmp + m, limit - m);
NTT(f, limit, 1); NTT(tmp, limit, 1); px(f, tmp, limit); NTT(f, limit, -1);
clr(f + T, limit - 1); clr(tmp, limit);
}
}P;
void getS() {
for (int i = 0; i <= k; i++) {
f[i] = mul((i & 1) ? mo - 1 : 1, invs[i]);
g[i] = mul(ksm(i, k), invs[i]);
}
P.times(f, g, k + 1, k + 1, k + 1);
for (int i = 0; i <= k; i++)
S[i] = f[i];
}
int main() {
freopen("graph.in", "r", stdin);
freopen("graph.out", "w", stdout);
P.Init();
scanf("%d %d", &n, &k);
getS();
int ans = 0, CC = 1, inv2 = ksm(2, mo - 2), sum2 = ksm(2, 1ll * n * (n - 1) / 2);
for (int i = 0; i <= k; i++) {
ans = add(ans, mul(S[i], mul(mul(CC, mul(sum2, ksm(inv2, i))), jc[i])));
CC = mul(CC, mul(n - 1 - i, inv[i + 1]));
}
printf("%d", mul(ans, n));
return 0;
}
标签:return,int,mo,YBT2023,invs,NTT,Day1,mul,inv
From: https://www.cnblogs.com/Sakura-TJH/p/YBT2023Day1_C.html