文章目录
一个非常好的题单。
本详解中，所有的题目的数据范围都经过了笔者的加强，而并不是原题的数据范围，这样可以促进读者更深的思考。
[集训队作业2013]城市规划
Description
求 n n n 个点的有标号无向连通图的数量。答案对 1004535809 1004535809 1004535809 取模。
n ≤ 1 0 6 n \le 10^6 n≤106 ，时限 2 s 2s 2s 。
Solution
首先考虑 n n n 个点的有标号无向图的数量 f ( n ) f(n) f(n) 。显然有 f ( n ) = 2 C n 2 f(n)=\text 2^{C_n^2} f(n)=2Cn2
n
n
n 个点的有标号无向连通图的数量
g
(
n
)
g(n)
g(n) 满足
∑
i
=
1
n
C
n
−
1
i
−
1
g
(
i
)
f
(
n
−
i
)
=
f
(
n
)
\sum_{i=1}^{n} C_{n-1}^{i-1}\ g(i) f(n-i)=f(n)
i=1∑nCn−1i−1 g(i)f(n−i)=f(n)
直接高斯消元是 O ( n 3 ) O(n^3) O(n3) 的。
考虑优化。我们拆开组合数，得到 ∑ i = 1 n g ( i ) ( i − 1 ) ! f ( n − i ) ( n − i ) ! = f ( n ) ( n − 1 ) ! \sum_{i=1}^n \frac {g(i)} {(i-1)!} \frac {f(n-i)} {(n-i)!}=\frac {f(n)} {(n-1)!} i=1∑n(i−1)!g(i)(n−i)!f(n−i)=(n−1)!f(n)
令 g ′ ( i ) = g ( i ) ( i − 1 ) ! g'(i)=\frac {g(i)} {(i-1)!} g′(i)=(i−1)!g(i)
f ′ ( i ) = f ( i ) i ! f'(i)=\frac {f(i)} {i!} f′(i)=i!f(i)
f ′ ′ ( i ) = f ( i ) ( i − 1 ) ! f''(i)=\frac {f(i)} {(i-1)!} f′′(i)=(i−1)!f(i)
令
G
′
,
F
′
,
F
′
′
G',F',F''
G′,F′,F′′分别为
g
′
,
f
′
,
f
′
′
g',f',f''
g′,f′,f′′ 的 OGF ，显然有
F
′
′
=
F
′
G
′
F''=F'G'
F′′=F′G′
即 G ′ = F ′ ′ × ( F ′ ) − 1 G'=F'' \times (F')^{-1} G′=F′′×(F′)−1
多项式求逆+多项式乘 即可求出 G ′ G' G′，然后再算回去不难得到答案。
时间复杂度 O ( n log n ) O(n \log n) O(nlogn) 。
CF438E: The Child and Binary Tree
Description
给定一个长度为 n n n 的正整数序列 A A A 。
一个二叉树可爱当且仅当这个二叉树上所有节点的点权都来自于 A A A 。
定义一棵二叉树的权值为这棵二叉树的所有节点的点权之和。
对于每个 i ∈ [ 1 , m ] i \in [1,m] i∈[1,m] ，分别求出权值为 i i i 的可爱二叉树的数量。答案对 998244353 998244353 998244353 取模。
n ≤ 1 0 6 , 1 ≤ A i , m ≤ 1 0 6 n \le 10^6, 1 \le A_i, m \le 10^6 n≤106,1≤Ai,m≤106 ，时限 2 s 2s 2s 。
Solution
令
f
(
i
)
f(i)
f(i) 为权值为
i
i
i 个可爱二叉树的数量，
g
(
i
)
=
[
i
∈
A
]
g(i)=[i \in A]
g(i)=[i∈A](即
i
i
i 是否在
A
A
A 中)。不难发现递推式
f
(
i
)
=
∑
j
=
1
m
[
j
∈
A
]
∑
k
=
0
i
−
j
f
(
k
)
f
(
i
−
j
−
k
)
f(i)=\sum_{j=1}^m [j \in A] \sum_{k=0}^{i-j} f(k)f(i-j-k)
f(i)=j=1∑m[j∈A]k=0∑i−jf(k)f(i−j−k)
令
F
,
G
F,G
F,G 分别为
f
,
g
f,g
f,g 的生成函数，那么
F
=
F
2
G
+
1
F=F^2G+1
F=F2G+1
大力解一元二次方程，得 F ( x ) = 1 ± 1 − 4 G 2 G F(x)=\frac {1 \ ± \ \sqrt {1-4G}} {2G} F(x)=2G1 ± 1−4G
由于生成函数的 0 0 0 次项应为 1 1 1 ，所以应取 − - − 。
但是，这个式子很难计算，因为 2 G 2G 2G 的常数项的系数可能是 0 0 0 ，这导致我们无法使用多项式求逆，而且分治NTT也被卡掉了。所以，我们不得不整理这个式子，使得需要求逆的部分的常数项一定不为 0 0 0 。
上下同乘
1
+
1
−
4
G
1+\sqrt {1-4G}
1+1−4G
得
F
(
x
)
=
2
1
−
4
G
F(x)=\frac {2} {\sqrt {1-4G}}
F(x)=1−4G
2
多项式开根+多项式求逆即可。
时间复杂度 O ( n log n ) O(n \log n) O(nlogn) 。
P4451 [国家集训队]整数的lqp拆分
Description
求 ∑ ∑ j = 1 m a j = n ∏ i = 1 m F a i \sum_{\sum_{j=1}^m a_j=n} \prod_{i=1}^m F_{a_i} ∑∑j=1maj=n∏i=1mFai 。这里 F F F 为斐波那契数列 ， F i F_i Fi 表示斐波那契数列的第 i i i 项。
n ≤ 1 0 1 0 7 n \le 10^{10^7} n≤10107，时限 1 s 1s 1s 。
Solution
暂咕。