闲话
截至本文撰写时，我多项式那篇已经写了 15k 了，而我甚至才刚介绍到分式分解
今日推歌是《夜行者们》洛天依／闹闹丶！
好今天又是水水水（
杂题
计数 \(n\) 个点、最大度数恰好为 \(m\) 的有标号无根树的数量。
\(n \le 10^5\)。
我们发现这个东西是恰好为 \(m\)。这个不好做。
但是我们可以求出最大度数不超过 \(m\) 的树的数量，然后作差分就能得到答案。
有标号无根树，考虑采用 prufer 序列。于是我们就需要计数 \(n - 2\) 长度、元素值域在 \([1, n]\) 内且每个元素出现次数不超过 \(m - 1\) 次的序列数。
这个可以对每个元素构造 EGF 后作卷积。可以发现每种元素对应的 EGF 相同，为
\[F(x) = \sum_{i=0}^{m-1} \frac{x^i}{i!} \]答案即为 \([x^{n-2}/(n-2)!] F^n(x)\)。
直接做就有 \(O(n\log n)/O(\frac{n\log^2 n}{\log \log n})\)。建议采用半在线卷积
带通配符单模式串多点匹配。
\(n,m \le 3\times 10^5\)。
基础题。
考虑形式化地表示从一个点处结束是否可以得到答案。取所有 \(*\) 为 \(0\)，得到 \(i\) 处结束的子串可以匹配等价于 \(A_i = 0\)，其中 \(A_i\) 的定义为
\[A_i = \sum_{p = 0}^{m - 1} (a_p - b_{i - m + p + 1}) a_p b_{i - m + p + 1} \]直接翻转 \(a\)，得到 \(a_{m - p - 1}\) 对应 \(b_{i - m + p + 1}\)，因此构造出了卷积形式。展开式子求解即可。
总时间复杂度 \(O(n\log n)\)。
对于每个 \(0\le k<mod\) 的整数 \(k\)，求出长度为 \(n\)，值域为 \([0,m]\) 且满足 \(\sum_{i=1}^na_i\equiv k\pmod{mod}\) 的序列 \(a\) 的个数。
\(1\le n,m\le10^6\)，\(1\le mod\le500\)，答案对 \(998244353\) 取模。
等写完多项式再来补（
小C有一个集合 \(S\)，里面的元素都是小于 \(m\) 的非负整数。他用程序编写了一个数列生成器，可以生成一个长度为 \(n\) 的数列，数列中的每个数都属于集合 \(S\)。
小C用这个生成器生成了许多这样的数列。但是小C有一个问题需要你的帮助：给定整数 \(x\)，求所有可以生成出的，且满足数列中所有数的乘积 \(\bmod \ m\) 的值等于 \(x\) 的不同的数列的有多少个。
小C认为，两个数列 \(A\) 和 \(B\) 不同，当且仅当 \(\exists i \text{ s.t. } A_i \neq B_i\)。另外，小C认为这个问题的答案可能很大，因此他只需要你帮助他求出答案对 \(1004535809\) 取模的值就可以了。
\(1 \le n \le 10^9\)，\(3 \le m \le 8000\)，\(1\le x < m\)。
假设 \(f_{i, j}\) 为当前选了 \(i\) 个数字，乘积 \(\bmod \ m\) 为 \(j\) 的数列的数量。容易写出转移
\[f_{i + j, k} = \sum_{a \times b \bmod m = k} f_{i, a} \times f_{j, b} \]我们发现这是个乘卷积(?)。考虑将卷积对象，即对应第二维的下标使用离散对数表示。
因此首先对 \(m\) 处理原根，随后生成每个值对应的原根的幂次，我们就能将条件转化成 \(g^{a + b} \mod m = g^k\)。直接做多项式乘法即可。这里需要注意的是，由于下标是 \(\bmod\ m\) 意义下的，因此需要作循环卷积。
总时间复杂度 \(O(n\log n)\)。
标签：le,数列,卷积,闲话,bmod,答案,23.1,log From： https://www.cnblogs.com/joke3579/p/chitchat230104.html