多项式求逆 +MTT...

Solution

去打了那个，3 模数 NTT。然后发现很多很多错误，因此稍微总结一下。

• 在 NTT 时求的 $n$ 必须要大于两个多项式最高系数非零项之和。
• 最大项其实约为 $10^{32}$，因此要上 4 模数 NTT 和__int128，还有__int128的O(1)快速乘... 当然用long long精度内 CRT 合并法也行，但我不会...
• lowgu 评测姬有毒...
• 还有各种精度玄学

还有一个问题就是 NOI 不准用__int128（在某场 LOJ 笔试比赛知道的），所以比较头疼

之后应该会去学一下拆系数吧。

Code

// Code by ajcxsu
// Problem: polyinv2

#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define CPY(x, y) memcpy(x, y, sizeof(x))
#define CLR(x, y) memset(x, y, sizeof(x))
#define MOD (1000000007ll)
using namespace std;

const int N=4e5+10;
template<typename T> inline void gn(T &x) {
    char ch=getchar(); x=0;
    while(!isdigit(ch)) ch=getchar();
    while(isdigit(ch)) x=x*10+ch-'0', ch=getchar();
}

template<typename T> T qmul(T x, T y, T mo) {
    return (x*y-(T)((__float128)x/mo*y)*mo+mo)%mo;
}

typedef long long ll;
ll qpow(ll x, ll y, ll mo) {
    ll ret=1;
    while(y) {
        if(y&1) ret=ret*x%mo;
        x=x*x%mo, y>>=1;
    }
    return ret;
}
namespace MTT {
    ll *f, *g, x[N], r[N];
    ll t1[N], t2[N];
    const int me=4;
    const ll mo[]={998244353, 469762049, 1004535809, 2281701377};
    __int128 ans[N], M[me], t[me];
    int n, m;
    void dft(ll x[], int d, ll mo) {
        for(int i=1;i<n;i++) if(r[i]>i) swap(x[r[i]], x[i]);
        ll t, w, o;
        for(int i=1;i<n;i<<=1) {
            o=qpow(3, (d*(mo-1)/(i<<1)+mo-1)%(mo-1), mo);
            for(int j=0;j<n;j+=(i<<1)) {
                w=1;
                for(int k=0;k<i;k++, w=w*o%mo)
                    t=x[i+j+k]*w%mo, x[i+j+k]=(x[j+k]-t+mo)%mo, (x[j+k]+=t)%=mo;
            }
        }
    }

    void fft(ll mo) {
        CPY(t2, g);
        dft(t1, 1, mo), dft(t2, 1, mo); for(int i=0;i<n;i++) x[i]=t1[i]*t2[i]%mo*t2[i]%mo;
        dft(x, -1, mo); ll inv=qpow(n, mo-2, mo); for(int i=0;i<=m;i++) x[i]=x[i]*inv%mo;
    }

    __int128 mt=1;
    void mtt(ll a[], ll b[], int deg) {
        f=a, g=b;
        n=m=deg;
        int l=0; m=n+m; for(n=1; n<=m; n<<=1) l++;
        for(int i=1;i<n;i++) r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
        CLR(ans, 0);
        for(int i=0;i<me;i++) {
            fill(t1, t1+n, 0); copy(a, a+deg, t1);
            fft(mo[i]);
            for(int j=0;j<deg;j++) (ans[j]+=qmul(__int128(x[j])*M[i], t[i], mt))%=mt;
        }
        for(int j=0;j<deg;j++) b[j]=(-(ans[j]%MOD)+2*b[j]%MOD+MOD)%MOD;
    }
    void ini() {
        for(int i=0;i<me;i++) mt*=mo[i];
        for(int i=0;i<me;i++) M[i]=mt/mo[i], t[i]=qpow(M[i]%mo[i], mo[i]-2, mo[i]);
    }
}

ll a[N], b[N];
void polyinv(int deg) {
    if(deg==1) { b[0]=qpow(a[0], MOD-2, MOD); return; }
    polyinv((deg+1)>>1);
    MTT::mtt(a, b, deg);
}

int main() {
    MTT::ini();
    int n;
    gn(n); for(int i=0;i<n;i++) gn(a[i]);
    polyinv(n);
    for(int i=0;i<n;i++) printf("%d ", b[i]);
    putchar('\n');
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/sol-luogu-4239.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆