bzoj 5093 图的价值

Posted on | Views:

第二类斯特林数 + $NTT$ .

每个点的贡献可以单独考虑,答案是 $1$ 个点的贡献 $\times n$ ,而 $1$ 个点的贡献可以通过枚举其度数计算.

公式不知道为啥炸了,只好贴图片了.

只用算后面那个 $s=\sum_{i=0}^{n-1} {n-1\choose i}\cdot i^k​$ .

为了方便,把这里的 $n$ 变成 $n-1$ ,即 $s=\sum_{i=0}^{n} {n\choose i}\cdot i^k$ .

套路地,考虑 $i^k$ 的组合意义,它表示将 $k$ 个不同的球放进 $i$ 个不同盒子中的方案数,盒子可以为空.

枚举有 $j$ 个盒子不为空.

而第二类斯特林数 $S(k,j) $ 表示将 $k$ 个球放入 $j$ 个相同的盒子中,盒子不能为空的方案数,于是得到
$$
i^k=\sum_{j=0}^{i-1}{i\choose j}\cdot S(k,j)\cdot j!
$$
代入 $s$ 的计算式,得到
$$
\begin{aligned}
s&=\sum_{i=0}^{n} \sum_{j=0}^{i-1} {i\choose j}\cdot j!\cdot S(k,j)\cdot {n\choose i} \\
&=\sum_{j=0}^{k} S(k,j)\cdot j!\cdot \sum_{i=0}^{n} {n\choose i}\cdot {i\choose j} \\
&=\sum_{j=0}^k S(k,j)\cdot j!\cdot {n\choose j} \cdot 2^{n-j}
\end{aligned}
$$
考虑利用容斥原理计算一行的斯特林数,
$$
S(n,m)=\frac{1}{m!}\sum_{i=0}^m (-1)^i {m\choose i}(m-i)^n \\
=\sum_{i=0}^m \frac{(-1)^i}{i!} \cdot \frac{(m-i)^n}{(m-i)!}
$$
用 $NTT$ 求出所有的 $S(k,j)$ ,直接带进去计算即可,时间复杂度 $O(k\log k)$ .

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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
//%std
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int P=998244353,G=3,inv2=(P+1)>>1;
int add(int a,int b)
{
	return (a+b>=P)?(a+b-P):(a+b);
}
void inc(int &a,int b)
{
	a=add(a,b);
}
int mul(int a,int b)
{
	return 1LL * a * b % P;
}
int fpow(int a,int b)
{
	int res=1;
	while(b)
	{
		if(b&1)
			res=mul(res,a);
		a=mul(a,a);
		b>>=1;
	}
	return res;
}
const int MAXN=8e5+10;
int rev[MAXN],omega[MAXN],inv[MAXN],curn;
void init(int n)
{
	for(int i=0;i<n;++i)
		rev[i]=(rev[i>>1]>>1)|((i&1)*(n>>1));
	for(int l=2; l<=n; l<<=1)
	{
		omega[l]=fpow(G,(P-1)/l);
		inv[l]=fpow(omega[l],P-2);
	}
	curn=n;
}
void DFT(int *a,int n,bool invflag)
{
	if(curn!=n)
		init(n);
	for(int i=0; i<n; ++i)
		if(i<rev[i])
			swap(a[i],a[rev[i]]);
	for(int l=2; l<=n; l<<=1)
	{
		int m=(l>>1);
		int gi=omega[l];
		if(invflag)
			gi=inv[l];
		for(int *p=a; p!=a+n; p+=l)
		{
			int g=1;
			for(int i=0; i<m; ++i)
			{
				int t=mul(g,p[i+m]);
				p[i+m]=add(p[i],P-t);
				p[i]=add(p[i],t);
				g=mul(g,gi);
			}
		}
	}
	if(invflag)
	{
		int invn=fpow(n,P-2);
		for(int i=0; i<n; ++i)
			a[i]=mul(a[i],invn);
	}
}
void NTT(int *A,int *B,int *C,int lenA,int lenB)
{
	static int a[MAXN],b[MAXN];
	int lenC=lenA+lenB-1,n=1;
	while(n<lenC)
		n<<=1;
	for(int i=0;i<lenA;++i)
		a[i]=A[i];
	for(int i=lenA;i<n;++i)
		a[i]=0;
	for(int i=0;i<lenB;++i)
		b[i]=B[i];
	for(int i=lenB;i<n;++i)
		b[i]=0;
	DFT(a,n,false);
	DFT(b,n,false);
	for(int i=0; i<n; ++i)
		C[i]=mul(a[i],b[i]);
	DFT(C,n,true);
}
int fac[MAXN],invfac[MAXN],Inv[MAXN];
void InitFac(int k)
{
	fac[0]=1;
	for(int i=1;i<=k;++i)
	{
		fac[i]=mul(fac[i-1],i);
		Inv[i]=(i==1)?1:mul(Inv[P%i],add(P,-P/i));
	}
	invfac[k]=fpow(fac[k],P-2);
	for(int i=k-1;i>=0;--i)
		invfac[i]=mul(invfac[i+1],i+1);
}
int S[MAXN],A[MAXN],B[MAXN];
int calc(int n,int k)
{
	for(int i=0;i<=k;++i)
	{
		A[i]=(i&1)?add(P,-invfac[i]):invfac[i];
		B[i]=mul(fpow(i,k),invfac[i]);
	}
	NTT(A,B,S,k+1,k+1);
	int s=0,binom=1,pw=fpow(2,n);
	for(int i=0;i<=k;++i)
	{
		int tmp=mul(S[i],fac[i]);
		tmp=mul(tmp,mul(binom,pw));
		inc(s,tmp);
		pw=mul(pw,inv2);
		binom=mul(binom,Inv[i+1]);
		binom=mul(binom,add(n,P-i));
	}
	return s;
}
int main()
{
	int n=read(),k=read();
	if(n==1)
		return puts("0")&0;
	InitFac(k);
	int ans=calc(n-1,k);
	ans=mul(ans,n);
	ans=mul(ans,fpow(2,1LL*(n-1)*(n-2)/2%(P-1)));
	cout<<ans<<endl;
	return 0;
}