图的价值

题目

首先可以单独计算一个点的贡献,最后乘上$n$。

那么我们可以列出柿子:

考虑它的意义:取出一个点,枚举它的度数,其他点可以随便连

然后这个式子并过不来这题

这个$\sum$前面部分处理起来比较方便,考虑化后面部分。

考虑一个柿子:

证明:左边表示把$k$个球放入n个不同的盒子中的方案数,右边表示枚举有$i$个盒子非空的方案,两者相等。(组合意义)

实际上这个式子的枚举上界因为$n$,但是改为$k$结果不变

知道这个柿子之后就可以化简

然后

证明:左边为$n-1$个人中选$i$个,$i$个中再轩$j$个,右边为先选出$j$个人,然后其他人是否被选择皆可(组合意义)

然后

然后用$NTT$算出斯特林数后即可

复杂度$O(klogk)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
/*
>Author: zxy_hhhh
>blog: zxy-hhhh.cn
>date: 2019/03/06
*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<cmath>
#include<map>
#include<set>
#include<vector>
#include<ctime>
#define rep(x,a,b) for (int x=int(a);x<=(int)(b);x++)
#define drp(x,a,b) for (int x=int(a);x>=(int)(b);x--)
#define cross(x,a) for (int x=hd[a];x;x=nx[x])
#define ll long long
using namespace std;
inline ll rd() {
ll _x=0;int _ch=getchar(),_f=1;
for(;!isdigit(_ch)&&(_ch!='-')&&(_ch!=EOF);_ch=getchar());
if (_ch=='-'){_f=-1;_ch=getchar();}
for(;isdigit(_ch);_ch=getchar()) _x=_x*10+_ch-'0';
return _f*_x;
}
void write(ll _x){if (_x>=10) write(_x/10),putchar(_x%10+'0'); else putchar(_x+'0'); }
inline void wrt(ll _x,char _p){if (_x<0) putchar('-'),_x=-_x; write(_x); if (_p) putchar(_p);}
#define maxn 800005
#define mod 998244353
#define inv2 499122177
#define g 3
int s[maxn];
int lim,l,r[maxn];
inline void init(int len, int type = 1) {
if (type) {
lim = 1, l = 0;
while (lim <= len) lim <<= 1, l++;
} else
lim = 1 << len, l = len;
rep(i, 0, lim - 1) r[i] = ((r[i >> 1] >> 1) | ((i & 1) << (l - 1)));
}
inline int Mod(int x) { return x < 0 ? x + mod : (x >= mod ? x - mod : x); }
inline int qpow(int x, ll k) {
int ans = 1;
for (; k; k >>= 1, x = 1ll * x * x % mod)
if (k & 1) ans = 1ll * ans * x % mod;
return ans;
}
inline void NTT(int *a, int type) {
rep(i, 0, lim - 1) if (i < r[i]) swap(a[i], a[r[i]]);
for (int mid = 1; mid < lim; mid <<= 1) {
int Wn = qpow(g, (mod - 1) / (mid << 1));
if (type == -1) Wn = qpow(Wn, mod - 2);
for (int R = mid << 1, j = 0; j < lim; j += R)
for (int k = 0, w = 1; k < mid; k++, w = 1ll * w * Wn % mod) {
int x = a[j + k], y = 1ll * w * a[j + mid + k] % mod;
a[j + k] = Mod(x + y);
a[j + mid + k] = Mod(x - y);
}
}
if (type == -1) {
int x = qpow(lim, mod - 2);
rep(i, 0, lim - 1) a[i] = 1ll * a[i] * x % mod;
}
}
int n,k;
int F[maxn],G[maxn],fac[maxn];
int main() {
n=rd(),k=rd();
fac[0]=1;
rep(i,1,k) fac[i]=1ll*fac[i-1]*i%mod;
rep(i,0,k) {
F[i]=1ll*((i&1)?998244352:1)*qpow(fac[i],mod-2)%mod;
G[i]=1ll*qpow(i,k)*qpow(fac[i],mod-2)%mod;
}
init(k+k);
NTT(F,1),NTT(G,1);
rep(i,0,lim-1) s[i]=1ll*F[i]*G[i]%mod;
NTT(s,-1);
int ans=0,sn=1,s2=qpow(2,n-1);
ans=1ll*s[0]*s2%mod;
rep(i,1,k) {
s2=1ll*s2*inv2%mod;
sn=1ll*sn*(n-i)%mod;
ans=(ans+1ll*s[i]*sn%mod*s2)%mod;
// wrt(ans,'\n');
}
wrt(1ll*ans*n%mod*qpow(2,1ll*(n-1)*(n-2)/2)%mod,'\n');
}
avatar
SDOI2017遗忘的集合