P3321 [SDOI2015]序列统计 做题记录

小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$ 取模的值就可以了。

我们设 $dp_{i,x}$ 表示长度为 $i$，$\operatorname{mod} m$ 的值为 $x$ 的不同序列的个数。那么有转移：

$dp_{i,x}=\sum\limits_{ab\mod m=x,b\in S}dp_{i-1,a}$

$=\sum\limits_{b\in S}dp_{i-1,\frac{x}{b}}$

设 $S'$ 为 $S$ 中所有元素的乘法逆元组成的集合，那么：

$=\sum\limits_{b\in S'}dp_{i-1,bx}$

发现很难求解，此路不通。

注意到”拦路虎“其实是乘法。我们并不会计算多项式的乘法卷积，只会计算多项式的加法卷积，那么我们不妨化乘法为加法，令 $S'=\{\log_g(u)|u\in S\}$（其中 $g$ 是 $m$ 的一个原根）即可，那么有:

$dp_{i,x}=\sum\limits_{b\in S'}dp_{i-1,x-b\mod p}$

设 $F_i=[i\in S']$，那么：

$=\sum\limits_{i=0}^xF_idp_{i-1,x-i\mod p}$

变成了卷积的形式！写得抽象点就是：

$dp_i=F*dp_{i-1}$

$=F^{i-1}*dp_1$

$=F^i$

那么多项式快速幂即可，不过注意到 $F$ 的长度很小，所以 $O(\log^2)$ 算法也可以被接受。

最后答案即为 $dp_{n,\log_g(x)}$，有一个细节就是算完卷积后要把后半部分加到前半部分，因为这是循环卷积。并且多项式的长度是 $m-1$。