NTT模板

短命女 2021-09-17 11:16 303阅读 0赞

//by waynetuinfor
    const int maxn = ;
    const int mod = ;
    const int root = ;
    
    
    template <long long mod, long long root>
    struct NTT { 
        vector<long long> omega;
        NTT() { 
            omega.resize(maxn + 1);
            long long x = fpow(root, (mod - 1) / maxn);
            omega[0] = 1ll;
            for (int i = 1; i <= maxn; ++i)
                omega[i] = omega[i - 1] * x % mod;
        }
        long long fpow(long long a, long long n) { 
            (n += mod - 1) %= mod - 1;
            long long r = 1;
            for (; n; n >>= 1) { 
                if (n & 1) (r *= a) %= mod;
                (a *= a) %= mod;
            }
            return r;
        }
        void bitrev(vector<long long> &v, int n) { 
            int z = __builtin_ctz(n) - 1;
            for (int i = 0; i < n; ++i) { 
                int x = 0;
                for (int j = 0; j <= z; ++j) x ^= (i >> j & 1) << (z - j);
                if (x > i) swap(v[x], v[i]);
            }
        }
        void ntt(vector<long long> &v, int n) { 
            bitrev(v, n);
            for (int s = 2; s <= n; s <<= 1) { 
                int z = s >> 1;
                for (int i = 0; i < n; i += s) { 
                    for (int k = 0; k < z; ++k) { 
                        long long x = v[i + k + z] * omega[maxn / s * k] % mod; 
                        v[i + k + z] = (v[i + k] + mod - x) % mod;
                        (v[i + k] += x) %= mod; 
                    }
                }
            }
        }
        void intt(vector<long long> &v, int n) { 
            ntt(v, n);
            for (int i = 1; i < n / 2; ++i) swap(v[i], v[n - i]);
            long long inv = fpow(n, -1);
            for (int i = 0; i < n; ++i) (v[i] *= inv) %= mod;
        }
        vector<long long> operator()(vector<long long> a, vector<long long> b) { 
            int sz = 1;
            while (sz < a.size() + b.size() - 1) sz <<= 1;
            while (a.size() < sz) a.push_back(0);
            while (b.size() < sz) b.push_back(0);
            ntt(a, sz), ntt(b, sz);
            vector<long long> c(sz);
            for (int i = 0; i < sz; ++i) c[i] = a[i] * b[i] % mod;
            intt(c, sz);
            while (c.size() && c.back() == 0) c.pop_back();
            return c;
        }
    };
    
    NTT<mod, root> conv;
    
    vector<long long> fpow(const vector<long long> &v, int n) { 
        if (n == 1) return v;
        vector<long long> res = fpow(v, n / 2);
        res = conv(res, res);
        if (n & 1) res = conv(res, v);
        return res;
    }

//by quailty
    typedef long long ll;
    const int MAXN=;
    const ll Mod=;
    const ll g=;
    void change(ll y[],int len)
    { 
        for(int i=1,j=len/2;i<len-1;i++)
        { 
            if(i<j)swap(y[i],y[j]);
            int k=len/2;
            while(j>=k)
            { 
                j-=k;
                k/=2;
            }
            if(j<k)j+=k;
        }
    }
    ll fp(ll a,ll k)
    { 
        if(k<0)
        { 
            a=fp(a,Mod-2);
            k=-k;
        }
        ll res=1;
        while(k)
        { 
            if(k&1)res=res*a%Mod;
            a=a*a%Mod;
            k>>=1;
        }
        return res;
    }
    void ntt(ll y[],int len,int on)
    { 
        change(y,len);
        for(int h=2;h<=len;h<<=1)
        { 
            ll wn=fp(g,-on*(Mod-1)/h);
            for(int j=0;j<len;j+=h)
            { 
                ll w=1;
                for(int k=j;k<j+h/2;k++)
                { 
                    ll u=y[k];
                    ll t=w*y[k+h/2]%Mod;
                    y[k]=(u+t)%Mod;
                    y[k+h/2]=(u-t+Mod)%Mod;
                    w=w*wn%Mod;
                }
            }
        }
        if(on==-1)
        { 
            ll t=fp(len,-1);
            for(int i=0;i<len;i++)
                y[i]=y[i]*t%Mod;
        }
    }