Chlience

【算法】NTT从入门到GG
本片博客中有很多前置知识,请一定要保证自己看懂,这样后面的学习会非常的轻松!!!剩余系剩余系指对于某一个特定的正整...
扫描右侧二维码阅读全文
23
2018/10

【算法】NTT从入门到GG

本片博客中有很多前置知识,请一定要保证自己看懂,这样后面的学习会非常的轻松!!!

剩余系

剩余系指对于某一个特定的正整数$n$,一个整数集中的数模$n$所得的余数域
如果一个剩余系中包含了这个正整数所有可能的余数,那么称之为模$n$的完全剩余系

简化剩余系是$n$的完全剩余系中与$n$互素的数构成的子集

群的阶数定义为集合$G$元素的个数,记作$|G|$

如果$G$只有有限个元素,称$G$为有限群

群的运算一般不可交换

满足交换律的群称为阿贝尔群(Abelian group)

模$n$的简化剩余系$Z_n^*$关于乘法构成的代数系统是群

封闭性:$gcd(ab , n) = gcd(ab\mod n , n) = 1$

结合律:乘法满足结合律

单位元:$e = 1$

逆元素:$ax\equiv 1\pmod n$在$Z_n^*$中有唯一解

子群

设$G$是群,$S$是$G$的一个子集,如果$S$仍然是群,或等价的满足
封闭性:$\forall a,b \in S , a * b \in S$
结合律:显然满足结合律
单位元:设$G$的单位元为$e$,有$e\in S$
逆元素:$\forall a \in S$,其在$G$中有逆元$a^{-1}$,$a^{-1}\in S$
则称$S$是$G$的一个子群
${e}$和$G$为$G$的平凡子群

陪集

设$H$为$G$的子群,$a \in G$,定义

$$aH = {ah|h\in H}$$

称$aH$是$H$的一个左陪集

$aH = \{ah , | h\in H\}$

显然的陪集中的元素与子集中的元素满足双射关系

$f(x) = ax , f(x)^{-1} = a^{-1}x$

加上自己的一点理解?

$a\in G , a^{-1}\in G , x_1\in H , x_2\in H$

若$a * x_1 \equiv b \pmod n , a * x_2 \equiv b \pmod n$

则$b \in G , b * a^{-1} = x_1 = x_2$

所以子集中的元素乘$a$后并不会映射到同一个元素上

同理, 陪集中的元素不会映射到同一个元素上

所以满足双射关系(自己理解和上面式子无关)

$|aH| = |H|$

若$a\in H$,则$aH = H$

$(aH = bH) \vee (aH \cap bH = \emptyset)$

即$aH$和$bH$不可能既不等价,又有交集

证明:

若使得$aH \cap bH \neq \emptyset$

必然有$ah_1 = bh_2$

$a = h_2 * h_1^{-1} * b$

$aH = bH * h_2 * h_1^{-1} = bH$

$\forall g \in G , g \in gH$

$G \subseteq \bigcup_{a\in G}aH$

显然的$\bigcup_{a\in G}aH \subseteq G$

所以

$$\bigcup_{a \in G}aH = G$$

即对于同一子集所形成的所有陪集的并等价于全集

陪集划分定理

假设有$a_1 , a_2 , \cdots , a_k \in G$

$G = \bigcup_{i = 1}^{k}a_iH$

其中$a_iH \cap a_jH = \emptyset (i\neq j)$

拉格朗日定理

根据陪集划分定理我们可以得到$k*|a_iH| = |G|$

即$k*|H| = |G| , |H| \mid |G|$

元素的幂

考虑有限群$G , a\in G$

元素的幂表示为$a^k = e\prod_{i=1}^{k}a , a^{-k} = e\prod_{i=1}^{k}a^{-1}$

使得$a_k = e$的最小正整数$d$称为$a$的阶,记作$ord(a)$

因为是个有限群,那么一定存在$ord(a)$

考虑由$a$的幂生成的集合$S = \{a_k|k\in Z\}$

显然$S$为$G$的子群

$|S| = ord(a) \Rightarrow ord(a) \mid |G|$

所以$a^{|G|} = a^{pord(a)} = (a^{ord(a)})^p = e^p = e$

$|Z_n^*| = \varphi(n)$

$\forall a\in Z_n^*$,(即$gcd(a , n) = 1$),有

$$a^{\varphi(n)} = 1 \pmod n$$

原根

对于群$G$,若$\exists g\in G$,使得$ord(g)=|G|$,称$g$为$G$的原根

$G$中每一个元素都是$g$的幂次

因为$g^k$在模$n$意义下有$|G|$种取值

对应了$G$中的$|G|$个元素

$Z_n^*$ 存在原根 $\Leftrightarrow n = 2 , 4 , p^a , 2p^a$,其中$p$为奇素数

如果存在原根,原根的数目为$\varphi(\varphi(n))$

考虑这样的素数$p = c * 2^l + 1$

运算都在$Z_p^*$中进行

对于$n = 2^k (k\leq l)$,令

$$g_n = g^{\frac{p - 1}{n}}$$

因为$p$为素数,所以$\varphi(p) = p - 1$,所以

$$g_n^n = g^{p-1} = 1$$

消去引理:$g_{dn}^{dk} = (g^{\frac{p-1}{dn}})^{dk} = (g^{\frac{p - 1}{n}})^k = g_n^k$

折半引理:$(g_n^k)^2 = (g_n^{k+\frac{n}{2}})^2 = g^{\frac{(p-1)k}{n}}$

求和引理:$\sum_{i = 0}^{n - 1} (g_n^k)^i = \begin{cases} n,n\mid k \\ 0,n\nmid k \end{cases}$

当$n\mid k$时,$g_n^k=(g^{\frac{p - 1}{n}})^{qn} = (g^{p - 1}) = 1$

当$n\nmid k$时,$g_n^k \neq 1 , \sum_{i = 0}^{n - 1} (g_n^k)^i = \frac{1 - g_n^{kn}}{1 - g_n^k } = 0$

可由等比数列递推公式得到

快速数论变换(NTT)

$g_n = g^{\frac{p - 1}{n}}$

$w_n = e^{\frac{2\pi i}{n}}$

$w_n \Leftrightarrow g_n$

将$DFT$修改为求$g_n^0 , g_n^1 , g_n^2 , \cdots , g_n^{n - 1}$处的点值

$IDFT$修改为求$g_n^0 , g_n^{- 1} , g_n^{- 2} , \cdots , g_n^{- (n - 1)}$处的点值

求原根

$g$为$Z_p^*$的原根$\Leftrightarrow ord(g) = p - 1$

由$ord(g) \mid (p - 1)$

设$p - 1$不同质因子为$p_1 , p_2 , \cdots , p_s$

$g$为原根$\Leftrightarrow g^{\frac{p - 1}{p_i}} \neq 1 , (i = 1 , 2 , \cdots , s)$

NTT中模数的选取

$c = a \otimes b$

$c_i = \sum_{j = 0} a_{i-j} b_j \pmod p$

如果$c_i < p$,显然结果是精确的

对于$p = c \times 2^k + 1$,必须满足$n \leq 2^k$

例:$p = 119*2^{23} + 1 = 998244353 , g = 3$

NTT题目

BZOJ 4555 求和

任意模数NTT(三模数NTT)

考虑长度为$n$($10^5$数量级)的向量在模$P$($10^9$数量级,可能非质数)意义下的卷积,即

$$c_i = \sum_{j = 0}^{i}a_{i - j} b_j \mod P$$

NTT的模数需要满足条件$P = c*2^k + 1$,为质数

由于$P$甚至不是质数,难以直接NTT,尝试直接计算出最终结果

$nP^2$的数量级为$10^{23} > 2^{64}$

那么我们取$int$范围内较大的三个不同的满足NTT条件的质数$p_1 , p_2 , p_3$,使得$p_1p_2p_3 > nP^2$,并分别在模$p_i$意义下进行卷积。设真实值为$s$,可以得到:

$$s \equiv s_1 \pmod {p_1}$$

$$s \equiv s_2 \pmod {p_2}$$

$$s \equiv s_3 \pmod {p_3}$$

前两项可以直接在$long long$范围内用CRT合并

$$s \equiv s_0 \pmod {p_1p_2}$$

令$s = s_0 + kp_1p_2 = s_3 + lp_3$

注意到$k < p_3$,将上式放至模$p_3$意义下,有

$$k \equiv (s_3 - s_0)(p_1p_2)^{-1} \pmod {p_3}$$

模$p_3$意义下所得即为$k$的真实值,随后在模$P$意义下回代得到$s\mod p$的值

板子

最后放上自己的板子

#include <bits/stdc++.h>
using namespace std;

int read() {
    int ans = 0 , flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag; 
}
const int mod = 1 + (119 << 23);
const int G = 3;

const int N = 1000010;
int a[N << 2] , b[N << 2];
int rev[N << 2];

int n , m;
int l;
int num[N << 2];

int qpow(int a , int b) {
    int ans = 1;
    while(b) {
        if(b & 1) {ans = 1ll * ans * a % mod;}
        a = 1ll * a * a % mod;
        b >>= 1;
    }
    return ans;
}

void ntt(int* now , int f) {
    for(int i = 0 ; i < n ; ++ i)
        if(i < rev[i])
            swap(now[i] , now[rev[i]]);
    for(int i = 1 ; i < n ; i <<= 1) {
        int gn = qpow(G , (mod - 1) / (i << 1));
        if(f != 1) gn = qpow(gn , mod - 2);
        for(int j = 0 ; j < n ; j += (i << 1)) {
            int x , y , g = 1;
            for(int k = 0 ; k < i ; ++ k , g = 1ll * g * gn % mod) {
                x = now[j + k]; y = 1ll * g * now[i + j + k] % mod;
                now[j + k] = (long long)(x + y) % mod;
                now[i + j + k] = (long long)(x - y + mod) % mod;
            }
        }
    }
    if(f != 1) {
        int ny = qpow(n , mod - 2);
        for(int i = 0 ; i < n ; ++ i) now[i] = 1ll * now[i] * ny % mod;
    }
}
int main() {
    n = read() , m = read();
    for(int i = 0 ; i <= n ; ++ i) a[i] = read();
    for(int j = 0 ; j <= m ; ++ j) b[j] = read();
    m += n;
    for(n = 1 ; n <= m ; n <<= 1) ++ l;
    for(int i = 0 ; i < n ; ++ i)
        rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (l - 1));
    ntt(a , 1); ntt(b , 1);
    for(int i = 0 ; i < n ; ++ i)
        a[i] = 1ll * a[i] * b[i] % mod;
    ntt(a , -1);
    for(int i=0;i<=m;++i)
        printf("%d ",a[i]);
    return 0;
}
Last modification:October 23rd, 2018 at 06:42 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment