旧题重做

[ZJOI2016]小星星

容斥是官方做法，不过用集合并卷积也可以推出同样的dp式子。

树形dp，令 $f_{x, i, S}$ 表示以 $x$ 为根的子树， $x$ 映射到 $i$ ，子树全体映射到 $S$ 的合法方案数。考虑给当前的 $x$ 添加一个以 $y$ 为根的子树，令新的以 $x$ 为根的 $d p$ 数组为 $f^{'}$ ，有：

f_{x, i, S}^{'} = \sum_{(i, j) \in E} \sum_{A \cup B = S, A \cap B = \emptyset} f_{x, i, A} f_{y, j, B}

枚举合法的 $i, j$ ，余下的就是一个看上去像子集卷积的东西。

然而最终只需要 $S$ 为全集的方案，如果 $A$ 与 $B$ 有交，那么 $A \cup B$ 必然小于新的 $x$ 的子树大小，最终不可能对答案产生贡献。

于是考虑去掉 $A \cap B = \emptyset$ 的限制，仍然保证答案的正确性，转化为集合并卷积:

f_{x, i, S}^{'} = \sum_{(i, j) \in E} \sum_{A \cup B = S} f_{x, i, A} f_{y, j, B}

于是令 $\hat{f}$ 表示 $f$ 对最后一维做莫比乌斯变换之后的结果，有：

{\hat{f}}_{x, i, S}^{'} = {\hat{f}}_{x, i, S} \sum_{(i, j) \in E} {\hat{f}}_{y, j, S}

初始状态下 $f_{x, i, S} = [S = {i}]$ ，很容易得到莫比乌斯变换之后的结果。dp中不需要进行反演，保留莫比乌斯变换后的形式计算即可。

最后将根的全集方案数用莫比乌斯逆变换的公式算出来即可，复杂度也是 $O (n^{3} 2^{n})$ 。

[CTS2019]重复

我们记 $t^{k}$ 表示将字符串 $t$ 重复 $k$ 次形成的字符串。

显然，我们先正难则反，统计不包含任何有意义字符串（简称为性质 $A$ ）的无限重复串的个数。

根据题意，可以设置一个只含有一个串 $s$ 的AC自动机。对于一个状态 $i$ ，有 $k_{i}$ 个字符可以转移到非根节点，假设是 $c_{i, 1}, c_{i, 2}, \dots, c_{i, k_{i}}$ ，且按照升序排序，剩余字符只能转移到根。那么不难发现，满足性质 $A$ 的串只能从 $\geq c_{i, k_{i}}$ 的字符中进行转移（称为合法转移），粗略考虑，发现我们需要统计的是长度为 $m$ 的字符串中，重复无限次仍然始终走合法转移的字符串有多少。

然而重复无限次不太具有可操作性，进一步观察一个串重复无限次后，在自动机上的转移规律。我们令 $t r a n s_{x, s}$ 表示从状态 $x$ 接受一个字符串 $s$ ，最终会走到什么状态。可以发现这样一个事实：当 $k$ 足够大的时候，必然有 $t r a n s_{0, t^{k}} = t r a n s_{0, t^{k + 1}} = t r a n s_{0, t^{k + 2}} = \dots$ ，这是因为所有可能在 $t^{k + 1}$ 的后缀中出现的 $s$ 的前缀一定被包含在 $t^{k}$ 的后缀中了。因此，如果记 $x = t r a n s_{0, t^{k}}$ ，我们就有理由定义 $t r a n s_{0, t^{\infty}} = x$ ，于是，在 $t$ 重复有限次之后，之后的转移都形如 $x \to t r a n s_{x, t [: 1]} \to t r a n s_{x, t [: 2]} \to \dots \to x$ ，然后不断重复。

不难发现 $t r a n s_{x, t} = x$ ，还可以证明满足这一点的 $x$ 是唯一的，因为如果满足这一点，那么就有 $t r a n s_{x, t^{k}} = x$ ，当 $k$ 足够大时， $x$ 一定被包含在 $t^{k}$ 的后缀中，于是就是唯一的。

另一个重要的事实： $t^{\infty}$ 满足性质 $A$ ，当且仅当 $x \to t r a n s_{x, t [: 1]} \to t r a n s_{x, t [: 2]} \to \dots \to x$ 都是合法转移。这是因为如果有一个有意义的串出现在了 $t^{\infty}$ 中，它一定会出现无限多次，于是一定会在不断重复的 $x \to t r a n s_{x, t [: 1]} \to t r a n s_{x, t [: 2]} \to \dots \to x$ 转移中出现，造成一个不合法的转移。

综上所述，我们可以先枚举 $x$ ，统计所有满足 $t r a n s_{x, t} = x$ 的串中，满足性质 $A$ 的串个数：令 $d p_{i, j}$ 表示长度为 $i$ 的满足 $t r a n s_{x, t} = j$ ，且都是合法转移的字符串 $t$ 的数目。转移方程容易得到，最后 $d p_{m, x}$ 就是答案。这个动态规划是 $O (n^{2} m)$ 的，还是无法通过本题。

再观察合法转移的性质：由于只能从 $\geq c_{i, k_{i}}$ 的字符中进行转移，因此每个点最多只有一个转移不走到根，也就是说，如果不走到根，那么合法转移的路径是唯一的。于是我们枚举从 $x$ 开始，一直走合法转移，第一次走到根的步数 $i$ 。令 $d p_{i, j}$ 表示长度为 $i$ 的满足 $t r a n s_{0, t} = j$ ，且都是合法转移的字符串 $t$ 的数目。这种情况的答案就是 $d p_{m - i, x}$ 。如果一次都没有回到根，这样的方案是唯一的，直接走就行。复杂度 $O (n m)$ 。

[CTS2019]珍珠

之前推的式子不够优雅！

一句话题意：求

a n s = n! \sum_{k = 0}^{n - 2 m} [y^{k}] [x^{n}] (\frac{e^{x} + e^{- x}}{2} + y \frac{e^{x} - e^{- x}}{2})^{D}

有了 $y$ 的指标作为辅助，推式子的过程可以精简很多：

a n s = \frac{n!}{2^{D}} \sum_{k = 0}^{n - 2 m} [y^{k}] [x^{n}] ((e^{x} + e^{- x}) + y (e^{x} - e^{- x}))^{D}

= \frac{n!}{2^{D}} \sum_{k = 0}^{n - 2 m} [y^{k}] [x^{n}] ((1 + y) e^{x} + (1 - y) e^{- x})^{D}

= \frac{n!}{2^{D}} \sum_{k = 0}^{n - 2 m} [y^{k}] [x^{n}] \sum_{i = 0}^{D} (\binom{D}{i}) e^{(2 i - D) x} (1 + y)^{i} (1 - y)^{D - i}

= \sum_{i = 0}^{D} (\binom{D}{i}) \frac{n!}{2^{D}} \sum_{k = 0}^{n - 2 m} [y^{k}] [x^{n}] e^{(2 i - D) x} (1 + y)^{i} (1 - y)^{D - i}

关键的一步是在枚举 $i$ 以后，一个二元混合多项式 $F (x, y)$ 被分离成 $F_{1} (x) F_{2} (y)$ 的形式，于是 $x$ 和 $y$ 的部分可以分离，并且 $x$ 的部分结果是显然的：

a n s = \sum_{i = 0}^{D} (\binom{D}{i}) \frac{n!}{2^{D}} ([x^{n}] e^{(2 i - D) x}) (\sum_{k = 0}^{n - 2 m} [y^{k}] (1 + y)^{i} (1 - y)^{D - i})

a n s = \sum_{i = 0}^{D} (\binom{D}{i}) \frac{(2 i - D)^{n}}{2^{D}} (\sum_{k = 0}^{n - 2 m} [y^{k}] (1 + y)^{i} (1 - y)^{D - i})

到了这一步就可以用分治fft大法 $O (n \log^{2} n)$ 解决问题了！但是如果想追求更好的做法，可以继续推导。下面关注对 $f_{i} = \sum_{k = 0}^{n - 2 m} [y^{k}] (1 + y)^{i} (1 - y)^{D - i}$ 的求和：

f_{i} = \sum_{j = 0}^{i} [y^{j}] (1 + y)^{i} \sum_{k = 0}^{n - 2 m - j} [y^{k}] (1 - y)^{D - i}

= \sum_{j = 0}^{i} (\binom{i}{j}) \sum_{k = 0}^{n - 2 m - j} (- 1)^{k} (\binom{D - i}{k}) = \sum_{j = 0}^{i} (\binom{i}{j}) (- 1)^{n - 2 m - j} (\binom{D - i - 1}{n - 2 m - j})

= i! (D - i - 1)! \sum_{j = 0}^{i} \frac{(- 1)^{n - 2 m - j}}{j! (n - 2 m - j)!} \frac{1}{(i - j)! (D - 1 - n + 2 m - (i - j))!}

最后就化成了一个卷积式，可以 $O (n \log n)$ 解决问题。可以发现 $(1 + y)^{k}$ 和 $(1 - y)^{k}$ 并不完全对称，因为 $(1 - y)^{k}$ 的系数前缀和有好的封闭形式。