概念引入

阶

对于$p \in N_+$且$(a, p) = 1$，满足$a^r \equiv 1 (mod p)$的最小的非负$r$为$a$模$p$意义下的阶，记作$\delta_p(a)$

原根

定义：若$p \in N_+$且$a \in N$，若$\delta_p(a) = \phi(p)$，则称$a$为模$p$的一个原根
相关定理：

  • 若一个数$m$拥有原根，那么它必定为$2, 4, p^t, 2p^t (p$为奇质数$)$的其中一个
    每个数$p$都有$\phi(\phi(p))$个原根
    　　证明：若$p \in N_+$且$(a, p) = 1$，正整数$r$满足$a^r \equiv 1 (mod p)$，那么$\delta(p) | r$，由此推广，可知$\delta(p) | \phi(p)$，所以$p$的原根个数即为$p$之前与$\phi(p)$互质的数，即$\phi(p)$故定理成立
    　　　　　　- 若$g$是$m$的一个原根，则$g, g^1, g^2, …, g^{\phi(m)} (mod p)$两两不同
    　　　　原根求法：
    　　将$\phi(m)$质因数分解，得$\phi(m) = p_1^{c_1} * p_2^{c_2} * … * p_k^{c_k}$
    　　那么所有$g$满足$g^{\frac{\phi(m)}{p_i}} \neq 1 (mod m)$即为$m$的原根

$NTT$

　　由于$FTT$涉及到复数的运算，所以常数很大，而$NTT$仅需使用长整型，可大大优化常数

　　能够将原根代替单位根进行计算，是因为它们的性质相似，至少在单位根需要的那几个性质原根都满足，当然，要能够进行$NTT$，需要满足模数$p$为质数，且$p = ax + 1$其中$x$为$2$的次幂，那么一般能满足条件的数（常用）有：
　　$| p | g |$

　　$| 469762049 | 3 |$

　　$| 998244353 | 3 |$

　　$| 1004535809 | 3 |$
　　那么，就可以将单位根$\omega_n$替换为$g^{\frac{p - 1}{n}}$进行$NTT$了

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>

#define MOD 998244353
#define g 3

using namespace std;

typedef long long LL;

const int MAXN = (1 << 22);

LL power (LL x, int p) {
    LL cnt = 1;
    while (p) {
        if (p & 1)
            cnt = cnt * x % MOD;

        x = x * x % MOD;
        p >>= 1;
    }

    return cnt;
}

const LL invg = power (g, MOD - 2);

int N, M;
LL A[MAXN], B[MAXN];

int oppo[MAXN];
int limit;
void NTT (LL* a, int inv) {
    for (int i = 0; i < limit; i ++)
        if (i < oppo[i])
            swap (a[i], a[oppo[i]]);
    for (int mid = 1; mid < limit; mid <<= 1) {
        int ome = power (inv == 1 ? g : invg, (MOD - 1) / (mid << 1));
        for (int n = mid << 1, j = 0; j < limit; j += n) {
            int x = 1;
            for (int k = 0; k < mid; k ++, x = x * ome % MOD) {
                LL a1 = a[j + k], xa2 = x * a[j + k + mid] % MOD;
                a[j + k] = (a1 + xa2) % MOD;
                a[j + k + mid] = (a1 - xa2 + MOD) % MOD;
            }
        }
    }
}

int getnum () {
    int num = 0;
    char ch = getchar ();

    while (! isdigit (ch))
        ch = getchar ();
    while (isdigit (ch))
        num = (num << 3) + (num << 1) + ch - '0', ch = getchar ();

    return num;
}

int main () {
    N = getnum (), M = getnum ();
    for (int i = 0; i <= N; i ++)
        A[i] = (int) getnum ();
    for (int i = 0; i <= M; i ++)
        B[i] = (int) getnum ();

    int n, lim = 0;
    for (n = 1; n <= N + M; n <<= 1, lim ++);
    for (int i = 0; i <= n; i ++)
        oppo[i] = (oppo[i >> 1] >> 1) | ((i & 1) << (lim - 1));
    limit = n;
    NTT (A, 1);
    NTT (B, 1);
    for (int i = 0; i <= n; i ++)
        A[i] = A[i] * B[i] % MOD;
    NTT (A, - 1);
    LL invn = power (n, MOD - 2);
    for (int i = 0; i <= N + M; i ++) {
        if (i)
            putchar (' ');
        printf ("%d", (int) (A[i] * invn % MOD));
    }
    puts ("");

    return 0;
}

任意模数$NTT$（三模数$NTT$法）

有公式

$$
\left\{\begin{aligned} x \equiv a_1 (mod m_1) \\ x \equiv a_2 (mod m_2) \\ x \equiv a_3 (mod m_3) \end{aligned}\right.
$$
直接乘会爆$long long$，就先将上面的用$CRT$合并，得

$$
\left\{\begin{aligned} x \equiv A (mod M) \\ x \equiv a_3 (mod m_3) \end{aligned}\right.
$$
那么设$Ans = kM + A$，则有
$$
\begin{aligned}
kM + A &\equiv a_3 \pmod{m_3} \\
k &\equiv (a_3 - A)M^{- 1} \pmod{m_3}
\end{aligned}
$$
直接处理即可

代码（任意模数$NTT$）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

typedef long long LL;

const int MAXN = (1 << 20);

const LL MOD[3]= {469762049, 998244353, 1004535809};
const LL g = 3;
const long double eps = 1e-03;

LL multi (LL a, LL b, LL p) {
    a %= p, b %= p;
    return ((a * b - (LL) ((LL) ((long double) a / p * b + eps) * p)) % p + p) % p;
}
LL power (LL x, LL p, LL mod) {
    LL cnt = 1;
    while (p) {
        if (p & 1)
            cnt = cnt * x % mod;

        x = x * x % mod;
        p >>= 1;
    }

    return cnt;
}
const LL invg[3]= {power (g, MOD[0] - 2, MOD[0]), power (g, MOD[1] - 2, MOD[1]), power (g, MOD[2] - 2, MOD[2])};

int N, M;
LL P;

LL A[MAXN], B[MAXN];

int limit;
int oppo[MAXN];
void NTT (LL* a, int inv, int type) {
    for (int i = 0; i < limit; i ++)
        if (i < oppo[i])
            swap (a[i], a[oppo[i]]);
    for (int mid = 1; mid < limit; mid <<= 1) {
        LL ome = power (inv == 1 ? g : invg[type], (MOD[type] - 1) / (mid << 1), MOD[type]);
        for (int n = mid << 1, j = 0; j < limit; j += n) {
            LL x = 1;
            for (int k = 0; k < mid; k ++, x = x * ome % MOD[type]) {
                LL a1 = a[j + k], xa2 = x * a[j + k + mid] % MOD[type];
                a[j + k] = (a1 + xa2) % MOD[type];
                a[j + k + mid] = (a1 - xa2 + MOD[type]) % MOD[type];
            }
        }
    }
}

LL ntta[3][MAXN], nttb[3][MAXN];
void NTT_Main () {
    int n, lim = 0;
    for (n = 1; n <= N + M; n <<= 1, lim ++);
    limit = n;
    for (int i = 0; i < n; i ++)
        oppo[i] = (oppo[i >> 1] >> 1) | ((i & 1) << (lim - 1));
    for (int i = 0; i < 3; i ++) {
        for (int j = 0; j < n; j ++)
            ntta[i][j] = A[j];
        for (int j = 0; j < n; j ++)
            nttb[i][j] = B[j];
        NTT (ntta[i], 1, i);
        NTT (nttb[i], 1, i);
        for (int j = 0; j < n; j ++)
            ntta[i][j] = ntta[i][j] * nttb[i][j] % MOD[i];
        NTT (ntta[i], - 1, i);
        LL invn = power (n, MOD[i] - 2, MOD[i]);
        for (int j = 0; j <= N + M; j ++)
            ntta[i][j] = ntta[i][j] * invn % MOD[i];
    }
}

LL ans[MAXN];
void CRT () {
    LL m = MOD[0] * MOD[1];
    LL M1 = MOD[1], M2 = MOD[0];
    LL t1 = power (M1, MOD[0] - 2, MOD[0]), t2 = power (M2, MOD[1] - 2, MOD[1]), invM = power (m % MOD[2], MOD[2] - 2, MOD[2]);
    for (int i = 0; i <= N + M; i ++) {
        LL a1 = ntta[0][i], a2 = ntta[1][i], a3 = ntta[2][i];
        LL A = (multi (a1 * M1 % m, t1 % m, m) + multi (a2 * M2 % m, t2 % m, m)) % m;
        LL k = ((a3 - A % MOD[2]) % MOD[2] + MOD[2]) % MOD[2] * invM % MOD[2];
        ans[i] = ((k % P * (m % P) % P + A % P) % P + P) % P;
    }
}

int getnum () {
    int num = 0;
    char ch = getchar ();

    while (! isdigit (ch))
        ch = getchar ();
    while (isdigit (ch))
        num = (num << 3) + (num << 1) + ch - '0', ch = getchar ();

    return num;
}

int main () {
    N = getnum (), M = getnum (), P = (LL) getnum ();
    for (int i = 0; i <= N; i ++)
        A[i] = (LL) getnum ();
    for (int i = 0; i <= M; i ++)
        B[i] = (LL) getnum ();

    NTT_Main ();
    CRT ();
    for (int i = 0; i <= N + M; i ++) {
        if (i)
            putchar (' ');
        printf ("%lld", ans[i]);
    }
    puts ("");

    return 0;
}