隐藏
「bzoj3625」小朋友和二叉树 - 生成函数+多项式开根+多项式求逆 | Bill Yang's Blog

路终会有尽头,但视野总能看到更远的地方。

0%

「bzoj3625」小朋友和二叉树 - 生成函数+多项式开根+多项式求逆

题目大意

    我们的小朋友很喜欢计算机科学,而且尤其喜欢二叉树。
    考虑一个含有$n$个互异正整数的序列$c[1],c[2],\ldots,c[n]$。如果一棵带点权的有根二叉树满足其所有顶点的权值都在集合$\lbrace c[1],c[2],\ldots,c[n]\rbrace$中,我们的小朋友就会将其称作神犇的。并且他认为,一棵带点权的树的权值,是其所有顶点权值的总和。
    给出一个整数$m$,你能对于任意的$s(1\le s\le m)$计算出权值为$s$的神犇二叉树的个数吗?请参照样例以更好的理解什么样的两棵二叉树会被视为不同的。
    我们只需要知道答案关于$998244353(7\cdot17\cdot2^{23}+1$,一个质数$)$取模后的值。


题目分析

注意到题目对结点个数无限制,故结点数趋于无穷时答案收敛。
对$C$做一个生成函数,记为$C(x)$,对答案做一个生成函数,记为$F(x)$。
利用答案收敛的性质,$F(x)$即非空树与空树的和,非空树即左右儿子$F(x)$与$C(x)$乘起来,空树即为$x^0=1$。

利用求根公式得到:

即:

多项式求逆必须要常数项存在逆(不为$0$)才存在解,故$\pm$只能取$+$。
即:

使用多项式开根与多项式求导即可。


代码

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
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

typedef long long LL;

inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}

const int maxn=262144+5;
const LL mod=998244353,g=3,inv2=499122177;

void check(LL &x) {
if(x>=mod)x-=mod;
if(x<0)x+=mod;
}

void add(LL &x,LL v) {
x+=v;
check(x);
}

LL Quick_Pow(LL a,LL b) {
LL sum=1;
for(; b; b>>=1,a=a*a%mod)if(b&1)sum=sum*a%mod;
return sum;
}

LL inv(LL x) {
return Quick_Pow(x,mod-2);
}

struct NumberTheoreticTransform {
int n,rev[maxn];
LL omega[maxn],iomega[maxn];

void init(int n) {
this->n=n;
int x=Quick_Pow(g,(mod-1)/n);
omega[0]=iomega[0]=1;
for(int i=1; i<n; i++) {
omega[i]=omega[i-1]*x%mod;
iomega[i]=inv(omega[i]);
}
int k=log2(n);
for(int i=0; i<n; i++) {
int t=0;
for(int j=0; j<k; j++)if(i&(1<<j))t|=(1<<(k-j-1));
rev[i]=t;
}
}

void transform(LL* a,LL* omega) {
for(int i=0; i<n; i++)if(i<rev[i])swap(a[i],a[rev[i]]);
for(int len=2; len<=n; len*=2) {
int mid=len>>1;
for(LL* p=a; p!=a+n; p+=len)
for(int i=0; i<mid; i++) {
LL t=omega[n/len*i]*p[mid+i]%mod;
p[mid+i]=p[i]-t,check(p[mid+i]);
add(p[i],t);
}
}
}

void dft(LL* a) {
transform(a,omega);
}

void idft(LL* a) {
transform(a,iomega);
LL x=inv(n);
for(int i=0; i<n; i++)a[i]=a[i]*x%mod;
}
} ntt;

void polynomial_inverse(const LL* a,const int n,LL* b) {
if(n==1) {
b[0]=inv(a[0]);
return;
}
polynomial_inverse(a,n>>1,b);
int p=n<<1;
static LL x[maxn];
copy(a,a+n,x),fill(x+n,x+p,0);
ntt.init(p),ntt.dft(x),ntt.dft(b);
for(int i=0; i<p; i++)b[i]=b[i]*((2-x[i]*b[i]%mod+mod)%mod)%mod;
ntt.idft(b),fill(b+n,b+p,0);
}

void polynomial_sqrt(const LL* a,const int n,LL* b) {
if(n==1) {
b[0]=1;
return;
}
polynomial_sqrt(a,n>>1,b);
int p=n<<1;
static LL inv_b[maxn],x[maxn];
fill(inv_b,inv_b+p,0);
polynomial_inverse(b,n,inv_b);
copy(a,a+n,x),fill(x+n,x+p,0);
ntt.init(p),ntt.dft(x),ntt.dft(b),ntt.dft(inv_b);
for(int i=0; i<p; i++)b[i]=(x[i]*inv_b[i]%mod+b[i])%mod*inv2%mod;
ntt.idft(b),fill(b+n,b+p,0);
}

int n,m;
LL C[maxn],sqrt_C[maxn],inv_sqrt_C[maxn];

int main() {
n=Get_Int();
m=Get_Int();
for(int i=1; i<=n; i++) {
int x=Get_Int();
if(x<=m)C[x]++;
}
C[0]=1;
for(int i=1; i<=m; i++)C[i]=(-4*C[i]%mod+mod)%mod;
int p=1;
while(p<(m+1))p<<=1;
polynomial_sqrt(C,p,sqrt_C);
fill(C+m+1,C+p,0);
add(sqrt_C[0],1);
polynomial_inverse(sqrt_C,p,inv_sqrt_C);
for(int i=1; i<=m; i++)printf("%lld\n",2*inv_sqrt_C[i]%mod);
return 0;
}
姥爷们赏瓶冰阔落吧~