NTT(快速数论变换)

NTT(快速数论变换)

在取模的情况下,解决多项式乘法.

n,m表示多项式的次数,从低到高读入

const int NR = 1 << 22, g = 3, gi = 332748118, mod = 998244353;
//998244353的一个原根为3且998244353-1=2^23*119，3在模998244353意义下的逆元为332748118
int n, m, rev[NR]; //rev[i]为i的二进制翻转
long long a[NR], b[NR];
ll fast_power(ll a, ll k) //快速幂，a为底数，k为指数
{
    ll res = 1;
    while (k)
    {
        if (k & 1)
            res = res * a % mod;
        a = a * a % mod;
        k >>= 1;
    }
    return res;
}
void NTT(ll* a, int n, int type) //NTT，type=1时系数表示法转点值表示法，否则点值表示法转系数表示法
{
    for (int i = 0; i < n; ++i) //先将a变成最后的样子
        if (i < rev[i])
            swap(a[i], a[rev[i]]);
    for (int i = 1; i < n; i <<= 1)
    {                                                            //在这之前NTT与FFT无异
        ll gn = fast_power(type ? g : gi, (mod - 1) / (i << 1)); //单位原根g_n
        for (int j = 0; j < n; j += (i << 1))                    //枚举具体区间，j也就是区间右端点
        {
            ll g0 = 1;
            for (int k = 0; k < i; ++k, g0 = g0 * gn % mod) //合并，记得要取模
            {
                ll x = a[j + k], y = g0 * a[i + j + k] % mod;
                a[j + k] = (x + y) % mod;
                a[i + j + k] = (x - y + mod) % mod;
            }
        }
    }
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i <= n; ++i) //输入第一个多项式
        scanf("%lld", a + i);
    for (int i = 0; i <= m; ++i) //输入第二个多项式
        scanf("%lld", b + i);
    int len = 1 << max((int)ceil(log2(n + m)), 1); //由于NTT需要项数为2的整数次方倍，所以多项式次数len为第一个大于n+m的二的正整数次方
    for (int i = 0; i < len; ++i)                  //求rev
        rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (max((int)ceil(log2(n + m)), 1) - 1));
    NTT(a, len, 1); //系数表示法转点值表示法
    NTT(b, len, 1);
    for (int i = 0; i <= len; ++i)
        a[i] = a[i] * b[i] % mod;          //O(n)乘法
    NTT(a, len, 0);                        //点值表示法转系数表示法
    ll inv = fast_power(len, mod - 2);     //inv为len的逆元（费马小定理求逆元）
    for (int i = 0; i <= n + m; ++i)       //输出
        printf("%lld ", a[i] * inv % mod); //除以len在模mod意义下即为乘以inv
    return 0;
}