$NTT$（快速数论变换）

- 概念引入

　　- 阶
　　　　对于$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$了

- 代码

 #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 = ( << );

 LL power (LL x, int p) {

     LL cnt = ;

     while (p) {

         if (p & )

             cnt = cnt * x % MOD;

         x = x * x % MOD;

         p >>= ;

     }

     return cnt;

 }

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

 int N, M;

 LL A[MAXN], B[MAXN];

 int oppo[MAXN];

 int limit;

 void NTT (LL* a, int inv) {

     for (int i = ; i < limit; i ++)

         if (i < oppo[i])

             swap (a[i], a[oppo[i]]);

     for (int mid = ; mid < limit; mid <<= ) {

         LL ome = power (inv ==  ? g : invg, (MOD - ) / (mid << ));

         for (int n = mid << , j = ; j < limit; j += n) {

             LL x = ;

             for (int k = ; 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 = ;

     char ch = getchar ();

     while (! isdigit (ch))

         ch = getchar ();

     while (isdigit (ch))

         num = (num << ) + (num << ) + ch - '', ch = getchar ();

     return num;

 }

 int main () {

     N = getnum (), M = getnum ();

     for (int i = ; i <= N; i ++)

         A[i] = (int) getnum ();

     for (int i = ; i <= M; i ++)

         B[i] = (int) getnum ();

     int n, lim = ;

     for (n = ; n <= N + M; n <<= , lim ++);

     for (int i = ; i <= n; i ++)

         oppo[i] = (oppo[i >> ] >> ) | ((i & ) << (lim - ));

     limit = n;

     NTT (A, );

     NTT (B, );

     for (int i = ; i <= n; i ++)

         A[i] = A[i] * B[i] % MOD;

     NTT (A, - );

     LL invn = power (n, MOD - );

     for (int i = ; i <= N + M; i ++) {

         if (i)

             putchar (' ');

         printf ("%d", (int) (A[i] * invn % MOD));

     }

     puts ("");

     return ;

 }

 /*

 1 2

 1 2

 1 2 1

 */

 /*

 5 5

 1 7 4 0 9 4

 8 8 2 4 5 5

 */

NTT

- 任意模数$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$，则有
　　

$kM + A \equiv a_3 (mod \ m_3)$

$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ k \equiv (a_3 - A)M^{- 1} (mod \ m_3)$

　　直接处理即可

- 代码（任意模数$NTT$）

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 using namespace std;

 typedef long long LL;

 const int MAXN = ( << );

 const LL MOD[]= {, , }; // 三模数

 const LL g = ;

 const long double eps = 1e-;

 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 = ;

     while (p) {

         if (p & )

             cnt = cnt * x % mod;

         x = x * x % mod;

         p >>= ;

     }

     return cnt;

 }

 const LL invg[]= {power (g, MOD[] - , MOD[]), power (g, MOD[] - , MOD[]), power (g, MOD[] - , MOD[])};

 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 = ; i < limit; i ++)

         if (i < oppo[i])

             swap (a[i], a[oppo[i]]);

     for (int mid = ; mid < limit; mid <<= ) {

         LL ome = power (inv ==  ? g : invg[type], (MOD[type] - ) / (mid << ), MOD[type]);

         for (int n = mid << , j = ; j < limit; j += n) {

             LL x = ;

             for (int k = ; 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[][MAXN], nttb[][MAXN];

 void NTT_Main () {

     int n, lim = ;

     for (n = ; n <= N + M; n <<= , lim ++);

     limit = n;

     for (int i = ; i < n; i ++)

         oppo[i] = (oppo[i >> ] >> ) | ((i & ) << (lim - ));

     for (int i = ; i < ; i ++) {

         for (int j = ; j < n; j ++)

             ntta[i][j] = A[j];

         for (int j = ; j < n; j ++)

             nttb[i][j] = B[j];

         NTT (ntta[i], , i);

         NTT (nttb[i], , i);

         for (int j = ; j < n; j ++)

             ntta[i][j] = ntta[i][j] * nttb[i][j] % MOD[i];

         NTT (ntta[i], - , i);

         LL invn = power (n, MOD[i] - , MOD[i]);

         for (int j = ; j <= N + M; j ++)

             ntta[i][j] = ntta[i][j] * invn % MOD[i];

     }

 }

 LL ans[MAXN];

 void CRT () {

     LL m = MOD[] * MOD[];

     LL M1 = MOD[], M2 = MOD[];

     LL t1 = power (M1, MOD[] - , MOD[]), t2 = power (M2, MOD[] - , MOD[]), invM = power (m % MOD[], MOD[] - , MOD[]);

     for (int i = ; i <= N + M; i ++) {

         LL a1 = ntta[][i], a2 = ntta[][i], a3 = ntta[][i];

         LL A = (multi (a1 * M1 % m, t1 % m, m) + multi (a2 * M2 % m, t2 % m, m)) % m;

         LL k = ((a3 - A % MOD[]) % MOD[] + MOD[]) % MOD[] * invM % MOD[];

         ans[i] = ((k % P * (m % P) % P + A % P) % P + P) % P;

     }

 }

 int getnum () {

     int num = ;

     char ch = getchar ();

     while (! isdigit (ch))

         ch = getchar ();

     while (isdigit (ch))

         num = (num << ) + (num << ) + ch - '', ch = getchar ();

     return num;

 }

 int main () {

     N = getnum (), M = getnum (), P = (LL) getnum ();

     for (int i = ; i <= N; i ++)

         A[i] = (LL) getnum ();

     for (int i = ; i <= M; i ++)

         B[i] = (LL) getnum ();

     NTT_Main ();

     CRT ();

     for (int i = ; i <= N + M; i ++) {

         if (i)

             putchar (' ');

         printf ("%lld", ans[i]);

     }

     puts ("");

     return ;

 }

 /*

 5 8 28

 19 32 0 182 99 95

 77 54 15 3 98 66 21 20 38

 */

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

巴特西