洛谷P3321 [SDOI2015]序列统计

考虑dp，$f_i(x)$表示用$i$个数表示出$x$来的方案数

$$ f_i(c) = \sum_{ab \equiv c\pmod m} f_{i / 2}(a) \times f_{i / 2}(b) $$

很像卷积，不过是乘法，需要将$ab$转化为$a+b$

$$ f_i(g^c) = \sum_{a + b \equiv c\pmod {m - 1}} f_{i / 2}(g^a) \times f_{i / 2}(g^b) $$

若$g$为$m$的原根，则$g^a$在模$m$意义下各不相同，可以与$a$形成一一映射关系，于是我们暴力找到一个原根$g$，将$S$中的元素$g^a$改为$a$即可

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>

#define int long long

using namespace std;

const int N = 2e6 + 10, M = 8e3 + 10, mod = 1004535809, inv3 = 334845270;

inline int read() {
    bool sym = 0; int res = 0; char ch = getchar();
    while (!isdigit(ch)) sym |= (ch == '-'), ch = getchar();
    while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
    return sym ? -res : res;
}

int n, m, G, S, inv[N], lg[N], lg2[N], f[40][N], W[2][40], rev[40][N], ans[N], a[N], b[N];

bool vis[M];

int MOD(int x) {while (x > mod) x -= mod; while (x < 0) x += mod; return x;}

int power(int a, int x) {
    int res = 1;
    while (x) {if (x & 1) res = 1ll * res * a % mod; a = 1ll * a * a % mod; x >>= 1;}
    return res;
}

bool check(int x) {
    memset(vis, 0, sizeof(vis)); int t = 1;
    for (int i = 0; i <= m - 2; i++, t = 1ll * t * x % m) {
        if (vis[t]) return 0; vis[t] = 1;
    }
    return 1;
}

void init() {
    int G, t = 1; n = inv[1] = 1; while (n < 2 * m) n <<= 1;
    for (int i = 2; i < m; i++) if (check(i)) {G = i; break;}
    for (int i = 0; i <= m - 2; i++) lg[t] = i, t = 1ll * t * G % m; m--;
    for (int i = 0; 1 << i <= n; i++) lg2[1 << i] = i;
    for (int i = 2; i <= n; i++) inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;
    for (int i = 0; 1 << i <= n; i++) {
        W[0][i] = power(inv3, (mod - 1) / (1 << i + 1));
        W[1][i] = power(3, (mod - 1) / (1 << i + 1));
        for (int j = 0; j < 1 << i; j++) rev[i][j] = rev[i][j >> 1] >> 1 | (j & 1 ? 1 << i - 1 : 0);
    }
}

void ntt(int a[], int opt) {
    for (int i = 0; i < n; i++) if (i < rev[lg2[n]][i]) swap(a[i], a[rev[lg2[n]][i]]);
    for (int i = 1; i < n; i <<= 1) {
        int t = W[opt][lg2[i]];
        for (int j = 0; j < n; j += i << 1) {
            int w = 1;
            for (int k = j; k < j + i; k++) {
                int x = a[k], d = 1ll * w * a[k + i] % mod;
                a[k] = MOD(x + d); a[k + i] = MOD(x - d); w = 1ll * w * t % mod;
            }
        }
    }
    if (!opt) for (int i = 0; i < n; i++) a[i] = 1ll * a[i] * inv[n] % mod;
}

void mul(int c[], int f[], int g[]) {
    memset(a, 0, sizeof(a)); for (int i = 0; i < m; i++) a[i] = f[i];
    memset(b, 0, sizeof(b)); for (int i = 0; i < m; i++) b[i] = g[i];
    ntt(a, 1); ntt(b, 1);
    for (int i = 0; i < n; i++) a[i] = 1ll * a[i] * b[i] % mod;
    ntt(a, 0);
    for (int i = 0; i < m; i++) c[i] = a[i];
    for (int i = m; i < n; i++) c[i % m] = MOD(c[i % m] + a[i]);
}

void solve(int x) {
    ans[0] = 1;
    for (int i = 30; i >= 0; i--) if (x >> i & 1) mul(ans, ans, f[i]);
}

signed main() {
    int n = read(); m = read(); G = read(); S = read(); init();
    for (int i = 1; i <= S; i++) {int x = read(); if (!x) continue; f[0][lg[x]]++;}
    for (int i = 1; i <= 30; i++) mul(f[i], f[i - 1], f[i - 1]);
    solve(n); printf("%lld", ans[lg[G]]);
    return 0;
}