[模板] 任意模数NTT

Code

#include <cstdio>
#include <algorithm>

typedef long long LL; const int N = 262150;
int a[N], b[N], n, m, nn, mm, pp, R[N], L, p[N], g[N]; LL f[2][N];

int read() {
    int x = 0; char c = getchar();
    while (c < '0' || c > '9') c = getchar();
    while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
    return x;
}
void exgcd(LL a, LL b, LL &x, LL &y) {
    if (!b) { x = 1, y = 0; return; }
    exgcd(b, a % b, y, x), y -= a / b * x;
}
LL ksm(LL a, LL b, LL p) {
    LL res = 1;
    for (; b; b >>= 1, a = 1LL * a * a % p)
        if (b & 1) res = 1LL * res * a % p;
    return res;
}
LL mul(LL a, LL b, LL p) {
    LL res = 0; int f = 1;
    if (a < 0) a = -a, f = -f; if (a >= p) a %= p;
    if (b < 0) b = -b, f = -f; if (b >= p) b %= p;
    for (; b; b >>= 1, a += a + a < p ? a : a - p)
        if ((b & 1) && (res += a) >= p) res -= p;
    return res * f; 
}
void NTT(LL *A, int f, int t) {
    for (int i = 0; i < n; ++i) if (i < R[i]) std::swap(A[i], A[R[i]]);
    for (int i = 1; i < n; i <<= 1) {
        int wn = ksm(f ? 3 : g[t], (p[t] - 1) / (i << 1), p[t]);
        for (int j = 0, r = i << 1; j < n; j += r) {
            int w = 1;
            for (int k = 0; k < i; ++k, w = 1LL * w * wn % p[t]) {
                int x = A[j + k], y = 1LL * w * A[i + j + k] % p[t];
                A[j + k] = (x + y) % p[t], A[i + j + k] = (x - y + p[t]) % p[t];
            }
        }
    }
}
void solve(int t, int k) {
    LL c[N] = {}, d[N] = {};
    for (int i = 0; i <= nn; ++i) c[i] = a[i];
    for (int i = 0; i <= mm; ++i) d[i] = b[i];
    NTT(c, 1, t), NTT(d, 1, t);
    for (int i = 0; i < n; ++i) f[k][i] = 1LL * c[i] * d[i] % p[t];
    NTT(f[k], 0, t);
    int inv = ksm(n, p[t] - 2, p[t]);
    for (int i = 0; i <= m; ++i) f[k][i] = 1LL * f[k][i] * inv % p[t];
}
int main() {
    nn = read(), mm = read(), pp = read();
    for (int i = 0; i <= nn; ++i) a[i] = read();
    for (int i = 0; i <= mm; ++i) b[i] = read();
    m = nn + mm; for (n = 1; n <= m; n <<= 1) ++L;
    for (int i = 0; i < n; ++i) R[i] = (R[i >> 1] >> 1) | ((i & 1) << (L - 1));
    p[1] = 469762049, p[2] = 998244353, p[3] = 1004535809;
    g[1] = 156587350, g[2] = 332748118, g[3] = 334845270;
    solve(1, 0), solve(2, 1);
    LL mod = 1LL * p[1] * p[2], x, y;
    exgcd(p[1], p[2], x, y), x = (x % mod + mod) % mod;
    for (int i = 0; i <= m; ++i) f[0][i] = (f[0][i] + mul(mul(x, f[1][i] - f[0][i] + mod, mod), p[1], mod)) % mod;
    solve(3, 1);
    LL inv = ksm(mod % p[3], p[3] - 2, p[3]);
    for (int i = 0; i <= m; ++i) printf("%lld ", (mul(((f[1][i] - f[0][i]) % p[3] + p[3]) * inv % p[3], mod, pp) + f[0][i]) % pp);
    return 0;
}

[模板] 任意模数NTT

原文：https://www.cnblogs.com/fly-in-milkyway/p/10554396.html