多项式求逆_牛客博客

一、模板 P4238 【模板】多项式求逆：
题目背景
模板题，无背景

题目描述
给定一个多项式 F(x) ，请求出一个多项式 G(x)，满足F(x)∗G(x)≡1(modxⁿ)。系数对 998244353 取模。

输入格式
首先输入一个整数 n，表示输入多项式的项数。
接着输入 n 个整数，第 i 个整数 ai代表F(x) 次数为 i−1 的项的系数。

输出格式
输出 n 个数字，第 i 个整数 bi代表 G(x) 次数为 i−1 的项的系数。保证有解。

输入输出样例
输入 #1 复制
5
1 6 3 4 9
输出 #1 复制
1 998244347 33 998244169 1020
说明/提示
1≤n≤1e5,0≤ai≤1e9

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#define ll long long
#define llu unsigned ll
#define int ll
using namespace std;
const int maxn=4e5+100;
const int p=998244353;
const int g=3;
int fi[maxn];
int a[maxn],b[maxn],c[maxn];

int mypow(int a,int b)
{
    if(b<0) return mypow(mypow(a,p-2),-b);
    int ans=1;
    while(b)
    {
        if(b&1) ans=ans*a%p;
        a=a*a%p;
        b>>=1;
    }
    return ans%p;
}

void ntt(int *x,int len,int f)
{
    for(int i=0;i<len;i++)
        if(i<fi[i]) swap(x[i],x[fi[i]]);

    for(int i=1;i<len;i<<=1)
    {
        int r=i<<1;
        int wn=mypow(g,f*(p-1)/r);
        for(int j=0;j<len;j+=r)
        {
            int w=1;
            for(int k=0;k<i;k++)
            {
                int xx=x[j+k],yy=w*x[j+i+k]%p;
                x[j+k]=((xx+yy)%p+p)%p;
                x[j+i+k]=((xx-yy)%p+p)%p;
                w=w*wn%p;
            }
        }
    }
    if(f==-1)
    {
        int invn=mypow(len,p-2);
        for(int i=0;i<len;i++)
            x[i]=x[i]*invn%p;
    }


}

void dfs(int n,int *a,int *b)
{
    if(n==1)
    {
        b[0]=mypow(a[0],p-2);
        return ;
    }
    dfs((n+1)>>1,a,b);
    int len=1,cnt=0;
    while(len<=(n<<1)) len<<=1,cnt++;
    for(int i=0;i<len;i++)
    {
        fi[i]=((fi[i>>1]>>1)|((i&1)<<(cnt-1)));
        c[i]=(i<n?a[i]:0);
    }
    ntt(c,len,1);
    ntt(b,len,1);
    for(int i=0;i<len;i++)
        b[i]=(2-c[i]*b[i]%p+p)%p*b[i]%p;
    ntt(b,len,-1);
    for(int i=n;i<len;i++)
        b[i]=0;

}


signed main(void)
{
    int n;//多项式项数
    scanf("%lld",&n);
    for(int i=0;i<n;i++)
        scanf("%lld",&a[i]);

    dfs(n,a,b);
    for(int i=0;i<n;i++)
        printf("%lld ",b[i]);
    putchar('\n');
    return 0;

}

2020/2/27 又更新了一下代码。
主要是在dfs（求逆）过程中 len 的取值问题。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#define ll long long
#define llu unsigned ll
#define int ll
using namespace std;
const int maxn=4e5+100;
const int p=998244353;
const int g=3;
int fi[maxn];
int a[maxn],b[maxn],c[maxn];

int mypow(int a,int b)
{
    if(b<0) return mypow(mypow(a,p-2),-b);
    int ans=1;
    while(b)
    {
        if(b&1) ans=ans*a%p;
        a=a*a%p;
        b>>=1;
    }
    return ans%p;
}

void ntt(int *x,int len,int f)
{
    for(int i=0;i<len;i++)
        if(i<fi[i]) swap(x[i],x[fi[i]]);

    for(int i=1;i<len;i<<=1)
    {
        int r=i<<1;
        int wn=mypow(g,f*(p-1)/r);
        for(int j=0;j<len;j+=r)
        {
            int w=1;
            for(int k=0;k<i;k++)
            {
                int xx=x[j+k],yy=w*x[j+i+k]%p;
                x[j+k]=((xx+yy)%p+p)%p;
                x[j+i+k]=((xx-yy)%p+p)%p;
                w=w*wn%p;
            }
        }
    }
    if(f==-1)
    {
        int invn=mypow(len,p-2);
        for(int i=0;i<len;i++)
            x[i]=x[i]*invn%p;
    }


}

void dfs(int n,int *a,int *b)
{
    if(n==1)
    {
        b[0]=mypow(a[0],p-2);
        return ;
    }
    dfs((n+1)>>1,a,b);
    int len=1,cnt=0;
    while(len<=((n-1)<<1)) len<<=1,cnt++;
    for(int i=0;i<len;i++)
    {
        fi[i]=((fi[i>>1]>>1)|((i&1)<<(cnt-1)));
        c[i]=(i<n?a[i]:0);
    }
    ntt(c,len,1);
    ntt(b,len,1);
    for(int i=0;i<len;i++)
        b[i]=(2-c[i]*b[i]%p+p)%p*b[i]%p;
    ntt(b,len,-1);
    for(int i=n;i<len;i++)
        b[i]=0;

}


signed main(void)
{
    int n;//多项式项数
    scanf("%lld",&n);
    for(int i=0;i<n;i++)
        scanf("%lld",&a[i]);

    dfs(n,a,b);
    for(int i=0;i<n;i++)
        printf("%lld ",b[i]);
    putchar('\n');
    return 0;

}