🔢 关键思路：从乘法到加法

题目要求序列中所有数的乘积模 (m) 等于 (x)。直接处理乘法比较困难，一个经典的技巧是利用原根将乘法运算转化为加法运算。

1. 寻找原根：因为 (m) 是质数，所以存在原根 (g)。原根 (g) 的性质是：(g^0, g^1, \dots, g^{m-2}) 模 (m) 的值恰好覆盖了 (1) 到 (m-1) 的所有整数。
2. 指标映射：对于任意非零数 (a) (即 (1 \leq a < m))，存在唯一的指数 (k) (在 (0) 到 (m-2) 之间) 使得 (g^k \equiv a \pmod{m})。这个 (k) 就是 (a) 关于原根 (g) 的指标，记作 (\text{ind}_g(a))。
3. 问题转化：利用对数的性质，数的乘积对应指标的和。因此，原问题 "数列所有数的乘积模 (m) 等于 (x)" 就转化为 "数列中所有非零数对应的指标之和模 (m-1) 等于 (\text{ind}_g(x))"。

🧮 生成函数与多项式快速幂

转化后的问题变成了：从集合 (S) 对应的指标集合中（忽略0），可重复地选取 (n) 个数，使得它们的和模 (m-1) 等于 (\text{ind}_g(x)) 的方案数。

1. 构造生成函数： 我们定义一个多项式 (A(x))，其中 (x^i) 的系数表示集合 (S) 中是否存在某个数，其指标为 (i)（存在则为1，否则为0）。更准确地说，系数表示选取一个数，其指标为 (i) 的方案数。 [ A(x) = \sum_{i=0}^{m-2} [\text{是否存在指标为 } i \text{ 的数}] \cdot x^i ]

2. 多项式快速幂：

   • 我们要求的是选 (n) 个数，其指标和模 (m-1) 为指定值。这相当于求生成函数 (A(x)) 的 (n) 次幂，即 ([A(x)]^n)。
   • 在计算过程中，多项式乘法是在模 (x^{m-1}-1) 意义下进行的循环卷积。这是因为指标和是在模 (m-1) 意义下的，多项式幂运算后，次数高于 (m-2) 的项需要循环累加到低次项上。
   • 直接计算多项式幂次（(n) 最大可达 (10^9)）需要使用快速幂技巧，每次乘法用NTT加速。模数 (1004535809) 是 NTT 友好型模数（原根为 3）。

3. 获取答案： 计算多项式 (F(x) = [A(x)]^n \pmod{x^{m-1}-1})，则 (x^{\text{ind}_g(x)}) 项的系数就是答案。

⚙️ 算法步骤与代码框架

1. 预处理：

   • 读入数据 (n, m, x, |S|) 和集合 (S)。
   • 寻找模数 (m) 的一个原根 (g)。
   • 构建指标映射表 ind，使得 ind[g^k % m] = k（其中 (k) 从 0 到 (m-2)）。

2. 构造初始多项式：

   • 初始化一个长度为 (m-1) 的多项式 poly，所有元素为 0。
   • 遍历集合 (S) 中的每个元素 (s)：
     • 如果 (s % m != 0) (题目中 (x \ge 1)，0 不会出现在合法序列中，可以忽略)，则令 poly[ind[s % m]] += 1。

3. 多项式快速幂：

   • 使用 NTT 进行多项式乘法，并在每次乘法后处理模 (x^{m-1}-1) 的循环卷积（将次数 (\geq m-1) 的项加到对应低次项上）。
   • 以快速幂的方式计算 poly 的 (n) 次方。

4. 输出结果：

   • 输出结果多项式 res 中 (x^{\text{ind}[x]}) 项的系数。

📝 核心代码片段（洛谷博客 hl666 的实现思路）

以下代码框架基于 hl666 的实现，展示了核心步骤：

#include <cstdio>
#define RI register int
using namespace std;
const int M = 8005, mod = 1004535809;

int n, m, x, |S|, root, A[M<<2], ind[M];
// ... 其他变量和函数声明

inline int quick_pow(int x, int r, int p=mod) { /* 快速幂 */ }
inline int get_root(int x) { /* 寻找原根 */ }

class Poly_Solver {
    private:
        int rev[M<<2], T[M<<2], lim, p;
        // ... 初始化、NTT、多项式乘法等函数
        inline void init(int n) { /* 初始化NTT */ }
        inline void NTT(int *f, int opt) { /* NTT变换 */ }
        inline void mul_self(int *A) { /* 多项式平方 */ }
        inline void mul(int *A, int *B) { /* 多项式乘法 */ }
    public:
        inline int pow(int *A, int r, int tar) { /* 多项式快速幂 */ }
}P;

int main() {
    scanf("%d%d%d%d", &n, &m, &x, &s);
    root = get_root(m); // 找到原根
    // 构建指标表
    for (int i = 0, cur = 1; i < m-1; ++i) {
        ind[cur] = i;
        cur = 1LL * cur * root % m;
    }
    // 构造初始多项式A
    for (int i = 0; i < s; ++i) {
        scanf("%d", &t);
        if (t != 0) A[ind[t]]++; // 忽略0
    }
    // 计算多项式快速幂，并输出x^{ind[x]}的系数
    printf("%d\n", P.pow(A, n, ind[x]));
    return 0;
}

（完整代码可参考 hl666 或 mrclr 的博客）

💡 注意事项与复杂度分析

• 原根的求法：可以预处理 (m-1) 的质因数，然后从 2 开始枚举 (g)，检查是否对所有质因子 (p) 都有 (g^{(m-1)/p} \not\equiv 1 \pmod{m})。
• 集合 (S) 中的 0：因为 (x \ge 1)，选取 0 会使乘积为 0，不可能等于 (x)，所以直接忽略。
• 时间复杂度：多项式乘法 (O(m \log m))，快速幂 (O(\log n))，总复杂度 (O(m \log m \log N))，对于 (m \leq 8000)，(n \leq 10^9) 可以接受。