【UR#3】链式反应

一道读题就很麻烦的题目,以下是简化版的题面:

给定 $n$ 和集合 $\mathbb{A}$,对于 $i=1..n$ 求多少 $i$ 个节点有标号的多叉树满足:

1、父亲节点的标号大于子节点。

2、一个点如果有儿子,则有两个无序的 $α$ 型儿子,有 $c$ 个无序的 $β$ 型儿子,其中$c∈\mathbb{A}$。

3、如果一个点是根节点或 $α$ 型儿子,那么它可以有儿子或者是一个叶节点;如果一个点是 $β$ 型儿子,那么它只能是一个叶节点。

$1\leq n\leq 2\cdot 10^5$ 。

考虑暴力 $dp$ ,设状态 $f_i$ 表示以 $i$ 为根时树的数量。那么有

但是注意到由于 $\alpha$ 型儿子是无序的,所以应该乘一个 $\frac{1}{2}$ 的常数。于是就可以获得一个 $40$ 分的 $O(n^3)$ 做法。

注意到可以把 $j$ 和 $k$ 分离,变成

展开两个二项系数

因为每次本质上只关心 $i-1-(j+k)$ 是否是 $\mathbb A$ 中的元素,所以即通过维护一个 $g$

然后转移就可以

这样就是 $O(n^2)$ 的了。可以喜提 $60pts$ 。

考虑放到同一个式子里观察:

那么如果设 $\mathbf{F}_i=\dfrac{f_i}{i!},\mathbf{P}_i=\dfrac{[i\in \mathbb{A}]}{i!}$,可以发现原式就是一个卷积的形式:

此时有两种不同的做法:

牛顿迭代

即发现本质上是在解一个这样的微分方程

然后迭就完了。复杂度 $O(n\log n)$ 但是常数…有点可怕。

技巧分治

这式子看上去就…十分的分治 FFT?但是注意到这是二卷积的形式。考虑最简单的分治 FFT 是单卷积,进行的操作可以看作是时间轴上的二进制拆分,即每次用已经得到实际结果的 $f_{l,l+1\cdots mid}$ 去更新 $f_{mid+1,mid+2\cdots r}$ 。考虑二卷积的时候,本质上与单卷积相同, 但需要分类讨论:

1、$l=1$ 时。

此时就是 $\mathbf{F}_{1…mid}^2$ 和 $\mathbf{P}_{0…r-l+1}$ 卷在一起。注意 $\mathbf{F}$ 中根据组合意义不能取第 $0$ 项。

2、$l>1$ 时。

发现此时由于分治了之后,要保证复杂度,似乎会出现需要用到 $i>mid$ 的 $f_i$ 的情况——但根据分治策略,此时一定有 $2\cdot l>r$ ,也就是 $\forall i\in[l,mid]\cap\mathbb{Z_+}$ ,$i>r-l-1\Longrightarrow r-imid$ 的那些转移点。所以此时就直接拿 $\mathbf{F}_{1…r-l}$ 卷上 $\mathbf{F}_{l…mid}$ 和 $\mathbf{P}_{1..r-l}$ 即可。注意到此时有别于 $l=1$ ,对于两棵子树的不同形态本质没有算重。所以为了处理方便可以在此时乘一个 $2$ 。

于是这种分治方式就比其他朴素的分治多一个比较优的常数。现在跑到了uoj榜的第一页。

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

int n ;
ll f[N] ;
ll g[N] ;
ll fac[N] ;
ll inv[N] ;
ll base[N] ;

const int Inv_2 = 499122177 ;

int expow(int x, int y){
int res = 1 ;
while (y){
if (y & 1)
res = (ll)res * x % P ;
x = (ll)x * x % P ; y >>= 1 ;
}
return res ;
}
void pre_do(){
fac[0] = inv[0] = 1 ;
for (ll i = 1 ; i <= n + 1 ; ++ i)
fac[i] = fac[i - 1] * i % P ;
inv[n + 1] = expow(fac[n + 1], P - 2) ;
for (ll i = n ; i >= 1 ; -- i)
inv[i] = inv[i + 1] * (i + 1ll) % P ;
}
int comb(int x, int y){
return (ll)fac[x] * inv[y] % P * inv[x - y] % P ;
}
void subtask1(){
f[1] = 1 ;
for (int i = 2 ; i <= n ; ++ i){
for (int j = 1 ; j <= i - 1 ; ++ j)
for (int k = 1, o ; k <= i - j - 1 ; ++ k)
if (base[i - j - k - 1]){
o = comb(i - 1, j) ;
o = 1ll * o * comb(i - j - 1, k) % P ;
add(f[i], 1ll * o * f[j] % P * f[k] % P) ;
}
f[i] = 1ll * f[i] * Inv_2 % P ;
}
for (int i = 1 ; i <= n ; ++ i) printf("%lld\n", f[i]) ; return ;
}
void subtask2(){
f[1] = 1 ; g[1] = 0 ;
for (int i = 2 ; i <= n ; ++ i){
for (int j = 1 ; j <= i - 1 ; ++ j)
if (base[i - j - 1])
add(f[i], 1ll * g[j] * inv[i - j - 1] % P) ;
f[i] = 1ll * f[i] * Inv_2 % P * fac[i - 1] % P ;
for (int j = 1 ; j <= i - 1 ; ++ j)
add(g[i], 1ll * f[i - j] * f[j] % P * inv[i - j] % P * inv[j] % P) ;
}
for (int i = 1 ; i <= n ; ++ i) printf("%lld\n", f[i]) ; return ;
}
namespace Poly{
int k, d ;
int rev[N] ;
ll g[20][N] ;
il ll expow(ll x, int y){
ll ret = 1 ;
while (y){
if (y & 1)
ret = ret * x % P ;
x = x * x % P ; y >>= 1 ;
}
return ret ;
}
void pre_rt(){
for (int i = 0 ; i < 20 ; ++ i){
ll* r = g[i], ut ; r[0] = 1 ;
ut = r[1] = expow(3, 998244352 / (1 << (i + 1))) ;
for (int j = 2 ; j < (1 << i) ; ++ j) r[j] = r[j - 1] * ut % P ;
}
}
template <typename T>
void NTT(T *f, int L, bool mk){
int l = 0 ;
for (int i = 0 ; i < L ; ++ i)
if (rev[i] < i) swap(f[i], f[rev[i]]) ;
for (int i = 1 ; i < L ; i <<= 1, ++ l){
ll *r = g[l], o = i << 1, rt, irt ;
for (int j = 0 ; j < L ; j += o)
for (int k = j ; k < i + j ; ++ k){
rt = f[k], irt = f[k + i] * r[k - j] % P ;
f[k] = addn(rt, irt), f[k + i] = decn(rt, irt) ;
}
}
if (!mk) return ;
reverse(f + 1, f + L) ;
int o = expow(L, P - 2) ;
for (int i = 0 ; i < L ; ++ i) (f[i] *= o) %= P ;
}
void getlen(int x){
d = 1, k = 0 ;
while (d <= x) d <<= 1, ++ k ;
for (int i = 0 ; i < d ; ++ i)
rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (k - 1)) ;
}
ll tl[N] ;
ll tr[N] ;
ll tmid[N] ;
void cdq(int l, int r){
if (l == r){
if (l == 1) f[1] = 1 ;
else f[l] = expow(2 * l, P - 2) * f[l] % P ;
return ;
}
int len = r - l + 1 ;
int mid = (l + r) >> 1 ;
int len1 = mid - l + 1 ;
cdq(l, mid) ; getlen(len * 2) ;
if (l <= 1){
memcpy(tl, base, sizeof(ll) * len) ;
memcpy(tr + 1, f + l, sizeof(ll) * len1) ;
memset(tl + len, 0, sizeof(ll) * (d - len + 1)) ;
memset(tr + len1 + 1, 0, sizeof(ll) * (d - len1 + 1)) ;
tr[0] = 0 ; NTT(tl, d, 0) ; NTT(tr, d, 0) ;
for (int i = 0 ; i < d ; ++ i)
(tl[i] *= tr[i] % P * tr[i] % P) %= P ;
NTT(tl, d, 1) ;
for (int i = mid + 1 ; i <= r ; ++ i) add(f[i], tl[i - l]) ;
}
else{
memcpy(tl, base, sizeof(ll) * len) ;
memcpy(tr + 1, f + l, sizeof(ll) * len1) ;
memcpy(tmid + 1, f + 1, sizeof(ll) * len) ;
memset(tl + len, 0, sizeof(ll) * (d - len + 1)) ;
memset(tr + len1 + 1, 0, sizeof(ll) * (d - len1 + 1)) ;
memset(tmid + len + 1, 0, sizeof(ll) * (d - len + 1)) ;
tmid[0] = tr[0] = 0 ; NTT(tl, d, 0) ; NTT(tmid, d, 0) ; NTT(tr, d, 0) ;
for (int i = 0 ; i < d ; ++ i)
(tl[i] *= tmid[i] % P * tr[i] % P) %= P ;
NTT(tl, d, 1) ;
for (int i = mid + 1 ; i <= r ; ++ i)
add(f[i], 2ll * tl[i - l] % P) ;
}
cdq(mid + 1, r) ;
}
}
int main(){
cin >> n ;
for (int i = 0 ; i < n ; ++ i)
scanf("%1lld", &base[i]) ; pre_do() ;
Poly :: pre_rt() ;
for (int i = 0 ; i < n ; ++ i)
base[i] = base[i] * inv[i] % P ; //debug(base, 0, n - 1) ;
f[1] = 1 ; Poly :: cdq(1, n) ;
for (int i = 1 ; i <= n ; ++ i)
printf("%lld\n", f[i] * fac[i] % P) ; return 0 ;
}