洛谷 P4721 [模板]分治FFT —— 分治FFT / 多项式求逆

时间：2023-03-09 00:25:13
洛谷 P4721 [模板]分治FFT —— 分治FFT / 多项式求逆

题目：https://www.luogu.org/problemnew/show/P4721

分治做法，考虑左边对右边的贡献即可；

注意最大用到的 a 的项也不过是 a[r-l] ，所以 NTT 可以只做到 2*(r-l)，能快一倍。

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long ll;

int const xn=(<<),mod=;

int n,f[xn],g[xn],a[xn],b[xn],rev[xn];

int rd()

{

  int ret=,f=; char ch=getchar();

  while(ch<''||ch>''){if(ch=='-')f=; ch=getchar();}

  while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();

  return f?ret:-ret;

}

ll pw(ll a,int b)

{

  ll ret=;

  for(;b;b>>=,a=(a*a)%mod)if(b&)ret=(ret*a)%mod;

  return ret;

}

int upt(int x){while(x>=mod)x-=mod; while(x<)x+=mod; return x;}

void ntt(int *a,int tp,int lim)

{

  for(int i=;i<lim;i++)

    if(i<rev[i])swap(a[i],a[rev[i]]);

  for(int mid=;mid<lim;mid<<=)

    {

      int wn=pw(,tp==?(mod-)/(mid<<):(mod-)-(mod-)/(mid<<));

      for(int j=,len=(mid<<);j<lim;j+=len)

    for(int k=,w=;k<mid;k++,w=(ll)w*wn%mod)

      {

        int x=a[j+k],y=(ll)w*a[j+mid+k]%mod;

        a[j+k]=upt(x+y); a[j+mid+k]=upt(x-y);

      }

    }

  if(tp==)return; int inv=pw(lim,mod-);

  for(int i=;i<lim;i++)a[i]=(ll)a[i]*inv%mod;

}

void work(int l,int r)

{

  if(l==r)return;

  int len=r-l+,mid=((l+r)>>);

  work(l,mid); int lim=,L=;

  while(lim<=(r-l))lim<<=,L++;//max:r-l

  for(int i=;i<lim;i++)rev[i]=((rev[i>>]>>)|((i&)<<(L-)));

  for(int i=;i<lim;i++)a[i]=b[i]=;//

  for(int i=l;i<=mid;i++)a[i-l]=f[i];

  for(int i=;i<len;i++)b[i]=g[i];

  ntt(a,,lim); ntt(b,,lim);

  for(int i=;i<lim;i++)a[i]=(ll)a[i]*b[i]%mod;

  ntt(a,-,lim);

  for(int i=mid+;i<=r;i++)f[i]=upt(f[i]+a[i-l]);

  work(mid+,r);

}

int main()

{

  n=rd(); f[]=;

  for(int i=;i<n;i++)g[i]=rd();

  work(,n-);

  for(int i=;i<n;i++)printf("%d ",f[i]); puts("");

  return ;

}

多项式求逆做法感觉很妙：

设 \( F(x) = \sum f_{i}*x_{i} \)，\( G(x) = \sum g_{i}*x_{i} \)

则 \( F(x) * G(x) = \sum x_{i} * \sum\limits_{j=0}^{i} f_{j}*g_{i-j} \)

即 \( F(x) * G(x) = F(x) - f_{0}*x_{0} \)

所以 \( F(x) = (1-G(x))^{-1} \)

多项式求逆即可。

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long ll;

int const xn=(<<),mod=;

int n,f[xn],g[xn],c[xn],rev[xn];

int rd()

{

  int ret=,f=; char ch=getchar();

  while(ch<''||ch>''){if(ch=='-')f=; ch=getchar();}

  while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();

  return f?ret:-ret;

}

ll pw(ll a,int b)

{

  ll ret=;

  for(;b;b>>=,a=(a*a)%mod)if(b&)ret=(ret*a)%mod;

  return ret;

}

int upt(int x){while(x>=mod)x-=mod; while(x<)x+=mod; return x;}

void ntt(int *a,int tp,int lim)

{

  for(int i=;i<lim;i++)

    if(i<rev[i])swap(a[i],a[rev[i]]);

  for(int mid=;mid<lim;mid<<=)

    {

      int p=mod-,len=(mid<<),wn=pw(,tp==?p/len:p-p/len);

      for(int j=;j<lim;j+=len)

    for(int k=,w=;k<mid;k++,w=(ll)w*wn%mod)

      {

        int x=a[j+k],y=(ll)w*a[j+mid+k]%mod;

        a[j+k]=upt(x+y); a[j+mid+k]=upt(x-y);

      }

    }

  if(tp==)return; int inv=pw(lim,mod-);

  for(int i=;i<lim;i++)a[i]=(ll)a[i]*inv%mod;

}

void inv(int *a,int *b,int n)

{

  if(n==){b[]=pw(a[],mod-); return;}

  inv(a,b,(n+)>>);

  int lim=,l=;

  while(lim<n+n)lim<<=,l++;

  for(int i=;i<lim;i++)rev[i]=((rev[i>>]>>)|((i&)<<(l-)));

  for(int i=;i<n;i++)c[i]=a[i];

  for(int i=n;i<lim;i++)c[i]=;

  ntt(c,,lim); ntt(b,,lim);

  for(int i=;i<lim;i++)b[i]=((ll)-(ll)c[i]*b[i])%mod*b[i]%mod;

  ntt(b,-,lim);

  for(int i=n;i<lim;i++)b[i]=;

}

int main()

{

  n=rd(); f[]=; g[]=;

  for(int i=;i<n;i++)g[i]=-rd();

  inv(g,f,n);

  for(int i=;i<n;i++)printf("%d ",f[i]); puts("");

  return ;

}

相关文章