P3321 [SDOI2015] 序列统计
问有多少个值域为 \([0,m-1]\) 的序列 \(A\) 满足 \(\prod_{i=1}^{n}A_i\equiv x(\operatorname{mod}m)\).
答案对 \(1004535809\) 取模。
\(1\le n\le 10^9\)，\(3\le m\le 8000\)，\(1\le x<m\).
保证 \(m\) 为质数。
最朴素的卷积显然是
\[f_{2i,c}=\sum_{ab\equiv c(\operatorname{mod}m)}f_{i,a}\cdot f_{i,b}
\]
时间复杂度 \(O(m^2\log n)\).
看到 \(1004535809\) 不难想到要进行一些操作。
不妨取对数，那么 \(a+b\equiv c(\operatorname{mod}m)\).
故可以将一个数 \(a\leftarrow \log_3a(\operatorname{mod}m)\).
那么
\[f_{2i,c}=\sum_{a+b\equiv c(\operatorname{mod}m)}f_{i,a}\cdot f_{i,b}
\]
把 \(0\sim 2m-1\) 放进去卷积即可。时间复杂度 \(O(m\log m\log n)\).
枚举 \(g^k\) 可以得到 \(g^k\rightarrow k\) 的映射。