Loj 6261 一个人的高三楼

Posted on | Views:

生成函数 + $NTT$ .

设这个数列做了 $i$ 次前缀和后的生成函数为 $F_i(x)$ . $F_0(x)$ 是已知的,将下标置为从 $0$ 开始.

考虑如何递推,令 $G(x)=\sum_{i=0}^{n-1}x^i$ ,则
$$
F_{i+1}(x)\equiv F_i(x)\cdot G(x)\ (\mbox{mod}\ x^n)
$$
那么就有
$$
F_k(x)\equiv F_0(x)\cdot G^k(x)\ (\mbox{mod}\ x^n)
$$
直接用多项式快速幂,时间复杂度 $O(n\log n)$ .但这种做法常数比较大,而且写起来麻烦.

考虑 $G(x)^k$ 的组合意义.有 $k$ 个盒子,每个盒子可以拿出 $0\sim n-1$ 个球, $[x^i]G^k(x)$ 表示拿出了 $i$ 个球的方案数.

盒子是不同的,而球是相同的,相当于把这 $i$ 个球分到 $k$ 个盒子里去.隔板法可知 $[x^i]G^k(x)={i+k-1\choose k-1}$ .

用 $NTT$ 将 $F_0(x)$ 和 $G^k(x)$ 乘起来就是答案了.时间复杂度 $O(n\log n)$ ,是与 $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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll read()
{
	ll out=0,sgn=1;
	char jp=getchar();
	while(jp!='-' && (jp<'0' || jp>'9'))
		jp=getchar();
	if(jp=='-')
		sgn=-1,jp=getchar();
	while(jp>='0' && jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*sgn;
}
const int P=998244353,G=3;
int add(int a,int b)
{
	return (a+b>=P)?(a+b-P):(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=1e5+10;
int omega[MAXN<<2],inv[MAXN<<2],rev[MAXN<<2],curn=0;
void init(int n)
{
	if(curn==n)
		return;
	for(int i=0; i<n; ++i)
		rev[i]=(rev[i>>1]>>1)|((n>>1)*(i&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)
{
	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);
	}
}
int NTT_A[MAXN<<2],NTT_B[MAXN<<2];
void NTT(int *A,int *B,int *C,int lenA,int lenB)
{
	int lenC=lenA+lenB-1,n=1;
	while(n<lenC)
		n<<=1;
	for(int i=0; i<lenA; ++i)
		NTT_A[i]=A[i];
	for(int i=lenA; i<n; ++i)
		NTT_A[i]=0;
	for(int i=0; i<lenB; ++i)
		NTT_B[i]=B[i];
	for(int i=lenB; i<n; ++i)
		NTT_B[i]=0;
	DFT(NTT_A,n,false);
	DFT(NTT_B,n,false);
	for(int i=0; i<n; ++i)
		C[i]=mul(NTT_A[i],NTT_B[i]);
	DFT(C,n,true);
}
int n;
ll k;
int A[MAXN],B[MAXN],C[MAXN<<2];
int main()
{
	n=read(),k=read();
	int t=(k-1)%P;
	for(int i=0; i<n; ++i)
		A[i]=read();
	B[0]=1;
	for(int i=1; i<n; ++i)
	{
		B[i]=mul(B[i-1],add(i,t));
		B[i]=mul(B[i],fpow(i,P-2));
	}
	NTT(A,B,C,n,n);
	for(int i=0; i<n; ++i)
		printf("%d\n",C[i]);
	return 0;
}