题目链接：Codeforces 438E

我们的小朋友很喜欢计算机科学，尤其喜欢二叉树。

考虑一个含有 $n$ 个互不相同的正整数序列 $c_1, c_2, \dots, c_n$。如果一棵带点权有根二叉树满足其所有节点的权值都属于集合 $\{c_1, c_2, \dots, c_n\}$ 中，那么小朋友就会将其称作「好的」。并且他认为，这棵二叉树的权值是所有节点的权值总和。

给出一个整数 $m$，你需要对于所有整数 $s \in [1, m]$，计算出权值为 $s$ 的「好的」二叉树数量。答案对 $998244353$ 取模。

数据范围：$1 \le n, m, c_i \le 10 ^ 5$。

Solution

构造 $g(x) = [x \in \{c_1, c_2, \dots, c_n\}]$，设 $f(x)$ 表示权值为 $x$ 的二叉树数量，则有递推式：

$$ f(n) = \begin{cases} 1 & n = 0 \\ \sum_{i = 0} ^ n g(i) \sum_{j = 0} ^ {n - i} f(j) \cdot f(n - i - j) & n > 0 \end{cases} $$

发现在 $n > 0$ 的情况下，$f(x)$ 的值就是一个卷机形式，那么我们考虑 $g, f$ 的生成函数：

$$ G(x) = \sum_{i = 0} ^ m [i \in \{c_1, c_2, \dots, c_n\}] \\ F = 1 + G \ast F \ast F $$

利用求根公式得到：

$$ F = \frac{1 \pm \sqrt{1 - 4G}}{2G} $$

由于 $G(0) = 0$ 使得分母 $2G$ 无法直接求逆，化为：

$$ F = \frac{2}{1 \mp \sqrt{1 - 4G}} $$

通过 $G(0) = 0, F(0) = 1$ 可以得到上式中 $\mp$ 应该取 $+$ 号。

套上多项式开根和求逆就行了。

时间复杂度：$\mathcal O(n + m \log m)$。

Code

/* 此处省略多项式模板 */

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    Vec G(m + 1, 0);
    for (int i = 1; i <= n; i++) {
        int x;
        scanf("%d", &x);
        if (x <= m) G[x] = 1;
    }
    Vec F = ~(sqrt(-G * 4 + 1) + 1) * 2;
    for (int i = 1; i <= m; i++) printf("%d\n", F[i]);
    return 0;
}