The Child and Binary Tree
题目描述
Our child likes computer science very much, especially he likes binary trees.
Consider the sequence of $n$ distinct positive integers: $c_1, c_2, \ldots, c_n$. The child calls a vertex-weighted rooted binary tree good if and only if for every vertex $v$, the weight of $v$ is in the set ${c_1, c_2, \ldots, c_n}$. Also our child thinks that the weight of a vertex-weighted tree is the sum of all vertices’ weights.
Given an integer $m$, can you for all $s \ (1 \le s \le m)$ calculate the number of good vertex-weighted rooted binary trees with weight $s$? Please, check the samples for better understanding what trees are considered different.
We only want to know the answer modulo $998244353$ ($7 \times 17 \times 2^{23}+1$, a prime number).
题意概述
有$n$种点，每种点有无限个，第$i$种点的权值为$c_i$。定义一棵二叉树的权值等于它所有点的权值之和。求对于所有$s \in [1, m]$，权值为$s$的二叉树有几棵。两棵二叉树不同当且仅当它们左子树或右子树不同，或者根节点权值不同。
数据范围：$1 \le n, m, c_i \le 10^5$。
算法分析
令$f(x)$表示权值为$x$的二叉树个数，$F(x)$为其生成函数（$F(x)=\sum_{i \ge 0} f(i)x^i$）。
令$C(x)$为给定$c$的集合的生成函数（$C(x)=\sum_{i=1}^n x^{c_i}$）。
根据 DP 转移方程，易知
$$
f(x)=\sum_{w \in {c_1, c_2, \ldots, c_n}} \sum_{i=0}^{x-w} f(i)f(x-w-i)
$$
即
$$
F(x)=C(x)F(x)^2+1
$$
解得
$$
F(x)={1 \pm \sqrt{1-4C(x)} \over 2C(x)}={2 \over 1 \pm \sqrt{1-4C(x)}}
$$
显然，若取减号，则当$x$趋近$0$时分母为$0$，因此只能取加号。接着就是多项式开根和多项式求逆了。
- 多项式求逆：求$GF \equiv 1 \pmod {x^n}$。
假设已知$G_0F \equiv 1 \pmod {x^{\lceil n/2 \rceil}}$
$G-G_0 \equiv 0 \pmod {x^{\lceil n/2 \rceil}}$
$G^2-2GG_0+G_0^2 \equiv 0 \pmod {x^n}$
$G-2G_0+G_0^2F \equiv 0 \pmod {x^n}$
$G \equiv 2G_0-G_0^2F \pmod {x^n}$
- 多项式开根：求$G^2 \equiv F \pmod {x^n}$。
假设已知$G_0^2 \equiv F \pmod {x^{\lceil n/2 \rceil}}$
$(G_0^2-F)^2 \equiv 0 \pmod {x^n}$
$(G_0^2+F)^2 \equiv 4G_0^2F \pmod {x^n}$
$\left({G_0^2+F \over 2G_0}\right)^2 \equiv F \pmod {x^n}$
$G \equiv {G_0+G_0^{-1}F \over 2} \pmod {x^n}$
代码
1 | |