Loading...

洛谷P4721 [模板]分治FFT

check评论:0 条 remove_red_eye浏览量:973 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2019-03-30

我用的求逆

我太菜了不会$cdq$自闭了就只能求逆了qwq

来推式子吧AB7tXT.png

$\huge f[i]=\sum\limits_{j=1}^j f[i-j]g[j]$

$\huge F(x)=\sum\limits_{i=0}^{∞} f[i]x^i\quad G(x)=\sum\limits_{i=0}^{∞} g[i]x^i​$

$\huge F(x)G(x)=\sum\limits_{i=0}^{\infty}\sum\limits_{j=0}^{\infty}f[i]g[j]x^{i+j} \quad 令k=i+j$

$\huge F(x)G(x)=\sum\limits_{k=0}^{\infty}\sum\limits_{j=0}^{k}f[k-j]g[j]x^k​$

$\huge 故F(x)G(x)=F(x)-f[0]​$

$\huge F(x)=\frac{f(0)}{1-G(x)}​$

然后求逆就好了AB7tXT.png

#include <bits/stdc++.h>
using namespace std;
const int mod=998244353,ge=3;
#define int long long
#define maxn 500050
int f[maxn],g[maxn],a[maxn],b[maxn],c[maxn],r[maxn],n,l,lim;
int ksm(int qaq,int f)
{
    int res=1;
    while(f)
    {
        if(f&1)
        {
            res=res*qaq%mod;
        }
        qaq=qaq*qaq%mod;
        f>>=1;
    }
    return res;
}
void NTT(int *x,int flag)
{
    for(int i=0;i<lim;i++)
    {
        if(i<r[i])
        {
            swap(x[i],x[r[i]]);
        }
    }
    for(int mid=1;mid<lim;mid<<=1)
    {
        int wn=ksm(ge,flag==1?(mod-1)/(mid<<1):(mod-1-(mod-1)/(mid<<1)));
        for(int i=0,r=(mid<<1);i<lim;i+=r)
        {
            int w=1;
            for(int k=0;k<mid;k++,w=w*wn%mod)
            {
                int m1=x[i+k],m2=x[i+mid+k]*w%mod;
                x[i+k]=(m1+m2)%mod,x[i+mid+k]=(m1-m2+mod)%mod;
            }
        }
    }
}
void getinv(int *a,int *b,int len)
{
    if(len==1)
    {
        b[0]=ksm(a[0],mod-2);
        return ;
    }
    getinv(a,b,(len+1)>>1);
    lim=1,l=0;
    while(lim<(len<<1))
    {
        lim<<=1,l++;
    }
    for(int i=1;i<lim;i++)
    {
        r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
    }
    for(int i=0;i<len;i++)
    {
        c[i]=a[i];
    }
    for(int i=len;i<lim;i++)
    {
        c[i]=0;
    }
    NTT(c,1),NTT(b,1);
    for(int i=0;i<lim;i++)
    {
        b[i]=b[i]*(2ll-c[i]*b[i]%mod+mod)%mod;
    } 
    NTT(b,0);
    int ny=ksm(lim,mod-2);
    for(int i=0;i<lim;i++)
    {
        b[i]=b[i]*ny%mod;
    }
    for(int i=len;i<lim;i++)
    {
        b[i]=0;
    }
}
main()
{
    cin>>n;
    for(int i=1;i<n;i++)
    {
        scanf("%lld",&g[i]);
        g[i]=(mod-g[i])%mod;
    }
    g[0]=1;
    getinv(g,f,n);
    for(int i=0;i<n;i++)
    {
        printf("%lld ",f[i]);
    }
}

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名