P4721 【模板】分治 FFT 题解


以下题解仅供学习参考使用。

抄袭、复制题解,以达到刷AC率/AC数量或其他目的的行为,在洛谷是严格禁止的。

洛谷非常重视学术诚信。此类行为将会导致您成为作弊者。具体细则请查看洛谷社区规则

评论

  • Ameyax
    小声bb两句。您TLE主要是因为$6logn$次$10^6$数组的memset,其次是模数没有const或者define,最后才是您fft里面复制数组的常数问题。
  • goodbye2018
    我的分治 FFT 总时间都不到 1 秒,不明白你为什么会 T:https://www.luogu.org/record/show?rid=8105397
  • Great_Influence
    好吧,是我naive了。看来我松得不够厉害,还要修行一波。@Fire_Storm 感谢指正。
  • Ameyax
    抱歉上面说错了其实qwq,您memset的次数是n,复杂度是n2。不能memset整个数组
  • 凄魉
    您好,现在你的代码只有分治这一部分,希望你能将程序的完整代码贴上便于理解,谢谢
  • Tyher
    您好,现在你的代码只有分治这一部分,希望你能将程序的完整代码贴上便于理解,谢谢 !
  • fzszkl
    cdqFFT还行。。不过算法过程确实是cdq分治的思想
  • Willem
    窝觉得 cdq分治 = 分治 QvQ
  • a2956331800
    初始化要memset(A,0,sizeof(int/long long)*len)啊
  • ylsoi
    常数国国王受我一拜
作者: Great_Influence 更新时间: 2018-07-04 15:45  在Ta的博客查看 举报    16  

都是求逆啊。。虽然可以理解。

分治$FFT$可以解决题目所描述的问题。

发现题目的要求类似于卷积,于是考虑使用$FFT$。

但是后面的数字基于前面的数字,无法快速计算,时间复杂度退化至$O(n^2)$。

于是我们考虑将类似的转移同时进行,来节省复杂度。

考虑利用分治。

假设我们求出了$l\to mid$的答案,要求这些点对$mid+1\to r$的影响,那么对右半边点$x$的贡献为:

$$w_x=\sum_{i=l}^{mid} f[i] * g[x-i]$$

这部分可以利用卷积来快速计算。计算完以后,答案直接加到答案数组就可以了。

需要注意的是,如果要求左边点对右边点的影响,首先整个区间以左对该区间的贡献应该先求出。所以分治过程为先分治左边,在求出中间,然后在递归右边。

时间复杂度$O(n\log^2n)$(被求逆$O(n\log n)$吊打)

有一个卡常技巧,就是可以发现你计算的时候只会用到 $md-l\sim r-l$ 的这一部分,前半部分不需要管。因此,直接用循环卷积对它进行处理,做乘法的时候不必做长度为 $1.5(r-l+1)$ 的,只需要做长度为 $r-l+1$ 的就可以了。这样常数会到原来的 $0.5\sim 0.67$ 倍(因为 $1.5(r-l+1)$ 的循环卷积通常会直接做长度为 $2(r-l+1) $ 的)。

upd:有人说要完整代码,我就放出来算了。。。

代码:

#include<cstdio>
#include<cstdlib>
#include<cctype>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cassert>
#include<iostream>
#define Rep(i,a,b) for(register int i=(a);i<=(b);++i)
#define Repe(i,a,b) for(register int i=(a);i>=(b);--i)
#define rep(i,a,b) for(register int i=(a);i<(b);++i)
#define pb push_back
#define mx(a,b) (a>b?a:b)
#define mn(a,b) (a<b?a:b)
typedef unsigned long long uint64;
typedef unsigned int uint32;
typedef long long ll;
using namespace std;

namespace IO
{
    const uint32 Buffsize=1<<15,Output=1<<24;
    static char Ch[Buffsize],*S=Ch,*T=Ch;
    inline char getc()
    {
        return((S==T)&&(T=(S=Ch)+fread(Ch,1,Buffsize,stdin),S==T)?0:*S++);
    }
    static char Out[Output],*nowps=Out;

    inline void flush(){fwrite(Out,1,nowps-Out,stdout);nowps=Out;}

    template<typename T>inline void read(T&x)
    {
        x=0;static char ch;T f=1;
        for(ch=getc();!isdigit(ch);ch=getc())if(ch=='-')f=-1;
        for(;isdigit(ch);ch=getc())x=x*10+(ch^48);
        x*=f;
    }

    template<typename T>inline void write(T x,char ch='\n')
    {
        if(!x)*nowps++='0';
        if(x<0)*nowps++='-',x=-x;
        static uint32 sta[111],tp;
        for(tp=0;x;x/=10)sta[++tp]=x%10;
        for(;tp;*nowps++=sta[tp--]^48);
        *nowps++=ch;
    }
}
using namespace IO;

void file()
{
#ifndef ONLINE_JUDGE
    FILE*DSD=freopen("water.in","r",stdin);
    FILE*CSC=freopen("water.out","w",stdout);
#endif
}

const int MAXN=1<<19;

namespace poly
{
    const int mod=998244353,gen=3;

    static int g[23][MAXN],iv[MAXN];

    inline int power(int u,int v)
    {
        register int sm=1;
        for(;v;v>>=1,u=(uint64)u*u%mod)if(v&1)
            sm=(uint64)sm*u%mod;
        return sm;
    }

    inline void predone()
    {
        Rep(i,1,18)
        {
            g[i][0]=1,g[i][1]=power(gen,(mod-1)>>i);
            Rep(j,2,2e5)g[i][j]=(ll)g[i][j-1]*g[i][1]%mod;
        }
    }

    static int Len,rev[MAXN];

    inline void calrev()
    {
        int II=log(Len)/log(2)-1;
        Rep(i,1,Len-1)rev[i]=rev[i>>1]>>1|(i&1)<<II;
    }

    inline int ad(int u,int v){return(u+=v)>=mod?u-mod:u;}

    inline void NTT(int*F,int typ)
    {
        Rep(i,1,Len-1)if(i<rev[i])swap(F[i],F[rev[i]]);
        for(register int i=2,ii=1,t=1;i<=Len;i<<=1,ii<<=1,++t)
            for(register int j=0;j<Len;j+=i)rep(k,0,ii)
            {
                register int tt=(uint64)*(F+j+k+ii)*g[t][k]%mod;
                *(F+j+k+ii)=ad(*(F+j+k),mod-tt);
                *(F+j+k)=ad(*(F+j+k),tt);
            }
        if(typ==-1)
        {
            reverse(F+1,F+Len);
            register uint64 invn=power(Len,mod-2);
            rep(i,0,Len)*(F+i)=invn**(F+i)%mod;
        }
    }
}
using poly::power;
using poly::Len;
using poly::calrev;
using poly::NTT;
using poly::mod;
using poly::predone;
using poly::ad;

static int n,F[MAXN],G[MAXN],A[MAXN],B[MAXN];

void cdq_FFT(int*F,int*G,int l,int r)
{
    if(l==r)
    {
        if(!l)F[l]=1;
        return;
    }
    int md=(l+r)>>1;
    cdq_FFT(F,G,l,md);
    memcpy(A,F+l,sizeof(int)*(md-l+1));
    memcpy(B,G,sizeof(int)*(r-l+1));
    for(Len=2;Len<=r-l+1;Len<<=1);
    calrev();
    memset(A+md-l+1,0,sizeof(int)*(Len-(md-l)));
    memset(B+r-l+1,0,sizeof(int)*(Len-(r-l)));
    NTT(A,1),NTT(B,1);
    rep(i,0,Len)A[i]=(ll)A[i]*B[i]%mod;
    NTT(A,-1);
    Rep(i,md+1,r)F[i]=ad(F[i],A[i-l]);
    cdq_FFT(F,G,md+1,r);
}

int main()
{
    file();
    predone();
    read(n);
    rep(i,1,n)read(G[i]);
    cdq_FFT(F,G,0,n-1);
    rep(i,0,n)write(F[i],' ');
    flush();
    return 0;
}

评论

  • Starrydream
    可以设g_0等于0吗
  • 星星之火
    建议您去掉第一句话,因为很容易让人不想往下看,其实写的蛮好的
  • 千年之狐_天才
    其实就几句话,我觉得去不去无所谓吧(逃
作者: nekko 更新时间: 2018-07-02 14:53  在Ta的博客查看 举报    15  

不太严谨+也许漏洞百出的题解

已知$\{g_{i} | i \in [1,n-1] \cap Z\}$,且$f_0=1$,同时有$f_i=\sum_{j=1}^{i}f_{i-j}g_j$

求$\{ f_i | i \in [0,n - 1] \cap Z \}$


不妨设$F(x)=\sum_{i=0}^{\infty}f_ix^i,G(x)=\sum_{i=0}^{\infty}g_ix^i$,且$g_0=0$

那么有$F(x)G(x)=\sum_{i=0}^{\infty}x^i\sum_{j+k=i}f_jg_k=F(x)-f_0x^0$

即$F(x)G(x) \equiv F(x)-f_0 (\bmod x^n)$

即$F(x) \equiv \frac{f_0}{1-G(x)} (\bmod x^n)$

即$F(X) \equiv (1-G(x))^{-1} (\bmod x^n)$

那么就是一个多项式求逆的模板了

评论

  • zhenglier
    %%%
  • namepsace_tsd
    好难啊
  • Starrydream
    这是NTT吧
作者: ljc1301 更新时间: 2019-01-14 09:59  在Ta的博客查看 举报    12  

分治fft的模板题干嘛用多项式求逆呢

讲一下(我理解的、可以做这道题)分治fft。

其实就是cdq分治的思路。每次求一个区间的时候,要保证这个区间左边所有值对这个区间的贡献都算出来了。每次把区间分为左右两半,先算做半段,然后用ntt计算左半段对右半段的贡献,再算右半度。

举个例子g[1..3]=1, 1, 0,求f[0..3](别问我干嘛要拿这个算斐波那契数列)

刚开始,是这样的(用中括号代表要算的区间,竖线代表中间的位置)

f =[1 0|0 0]

先算左边

f =[1|0]0 0

左半边的长度为1,不往下递归。计算左区间对右区间的贡献。就是把1, 0和g的前两项0, 1做卷积,得到*, 1(星号代表我们不在意这个位置),再把得到的后半段加到这个区间的右半边。操作后:

f =[1|1]0 0

右半边的长度为1,不往下递归。这一步就好了,回到上一步。

f =[1 1|0 0]

计算左半边对右半边的贡献。把1, 1, 0, 0和g的前四项0, 1, 1, 0做卷积,得到*, *, 2, 1,再把得到的后半段加到这个区间的右半边。操作后:

f =[1 1|2 1]

现在开始计算右半段。

f = 1 1[2|1]

左半边的长度是1,不往下递归。计算左区间对右区间的贡献。就是把2, 0(注意这里是0)和g的(不是后)两项0, 1做卷积,得到*, 2,再把得到的后半段到这个区间的右半边。操作后:

f = 1 1[2|3]

右半边的长度为1,不往下递归。然后这个f数组就算好了。

代码(我是先填充成2的幂,这样好写):

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxlogn=18;
const int maxn=(1<<maxlogn)|1;
const int G0=15311432;
const int kcz=998244353;
int n,rev[maxn];
ll G[2][24],f[maxn],g[maxn],a[maxn],b[maxn];
void gcd(ll a,ll b,ll &x,ll &y)
{
    if(!b) x=1,y=0;
    else gcd(b,a%b,y,x),y-=x*(a/b);
}
inline ll inv(ll a)
{
    ll x,y;
    gcd(a,kcz,x,y);
    return (x+kcz)%kcz;
}
inline void calcrev(int logn)
{
    register int i;
    rev[0]=0;
    for(i=1;i<(1<<logn);i++)
        rev[i]=(rev[i>>1]>>1)|((i&1)<<(logn-1));
}
inline void FFT(ll *a,int logn,int flag)
{
    register int i,j,k,mid;
    register ll t1,t2,t;
    for(i=0;i<(1<<logn);i++)
        if(rev[i]<i)
            swap(a[rev[i]],a[i]);
    for(i=1;i<=logn;i++)
        for(mid=1<<(i-1),j=0;j<(1<<logn);j+=1<<i)
            for(k=0,t=1;k<mid;k++,t=t*G[flag][i]%kcz)
            {
                t1=a[j|k],t2=t*a[j|k|mid];
                a[j|k]=(t1+t2)%kcz,a[j|k|mid]=(t1-t2)%kcz;
            }
}
void solve(int l,int r,int logn)
{
    if(logn<=0) return;
    if(l>=n) return;
    int mid=(l+r)>>1,i;
    ll t=inv(r-l);
    solve(l,mid,logn-1); // 计算左区间
    calcrev(logn);
    memset(a+(r-l)/2,0,sizeof(ll)*(r-l)/2); // 拷贝左区间
    memcpy(a,f+l,sizeof(ll)*(r-l)/2); // 填充0
    memcpy(b,g,sizeof(ll)*(r-l)); // 拷贝g
    FFT(a,logn,0),FFT(b,logn,0); // 卷积
    for(i=0;i<r-l;i++) a[i]=a[i]*b[i]%kcz;
    FFT(a,logn,1);
    for(i=0;i<r-l;i++) a[i]=a[i]*t%kcz;
    for(i=(r-l)/2;i<r-l;i++)
        f[l+i]=(f[l+i]+a[i])%kcz; // 把卷积后的右半段的数加到f数组后半段
    // 可能你会注意到,这个卷积是(r-l)/2的长度卷一个r-l的长度,而我卷积时最终结果当作r-l的长度来存,这会不会有影响?注意到超出部分是(r-l)/2左右,根据fft的实现,超出部分是会重新从0开始填的,所以只会影响结果的前半段,与后半段无关
    solve(mid,r,logn-1); // 计算右区间
}
int main()
{
    int logn,i;
    G[1][23]=inv(G[0][23]=G0);
    for(i=22;i>=0;i--)
    {
        G[0][i]=G[0][i+1]*G[0][i+1]%kcz;
        G[1][i]=G[1][i+1]*G[1][i+1]%kcz;
    }
    scanf("%d",&n);
    for(logn=0;(1<<logn)<n;logn++);
    for(i=1;i<n;i++) scanf("%lld",&g[i]);
    for(i=0;i<n;i++) f[i]=!i;
    solve(0,1<<logn,logn);
    for(i=0;i<n;i++)
        printf("%lld ",(f[i]+kcz)%kcz);
    printf("\n");
    return 0;
}

评论

  • jyz1232012
    题解的倒数第三行写错了,边界条件g0就是0啊,但是你代码里面需要令g0=1才能AC,是因为你需要求逆的式子是1-g(x),而不是-g(x)。
  • shadowice1984
    感谢提醒,已经fix
作者: shadowice1984 更新时间: 2018-07-02 17:17  在Ta的博客查看 举报    12  

多项式求逆大法好!


如果你不会生成函数那一套理论请左转问度娘

我们考虑万能的生成函数……来求这个多项式f

假设这个多项式的生成函数是$f(x)$那么我们就是要求这个多项式的生成函数

然后我们呢发现这个生成函数$f(x)$有一个非常棒的特点,就是它卷积一个$g(x)$之后整体向右移了一位

所以我们可以列出这样一个多项式方程

$f(x)g(x)+f_{0}=f(x)$

然后移项

$(1-g(x))f(x)=f_{0}$

由于我们只需要求出$f(x)$的前n项,所以我们可以在膜$x^{n}$的意义下进行运算

$(1-g(x))f(x) \equiv f_{0} (modx^n)$

此时我们就可以两边同时乘逆元啦……

$f(x) \equiv f_{0}(1-g(x))^{-1} (mod x^n)$

剩下的事情就是左转隔壁“【模板】 多项式求逆”然后粘一遍板子的事情啦……

上代码~

#include<cstdio>
#include<algorithm>
using namespace std;const int N=262144+10;typedef unsigned long long ll;const ll mod=998244353;
int rv[N];ll rt[2][20];ll tr1[N];ll tr2[N];ll g[N];ll ig[N];int Len;int n;
inline ll po(ll a,ll p){ll r=1;for(;p;p>>=1,a=a*a%mod)if(p&1)r=r*a%mod;return r;}
inline void ntt(ll* a,int o,int len)//ntt
{
    for(int i=0;i<len;i++)if(i<rv[i])swap(a[i],a[rv[i]]);ll a0,a1;
    for(int k=1,j=1;k<len;k<<=1,j++)
        for(int s=0;s<len;s+=(k<<1))
            for(int i=s,w=1;i<s+k;i++,w=w*rt[o][j]%mod)
            a0=a[i],a1=w*a[i+k]%mod,a[i]=(a0+a1)%mod,a[i+k]=(a0+mod-a1)%mod;
    if(o==1){ll inv=po(len,mod-2);for(int i=0;i<len;i++)(a[i]*=inv)%=mod;}
}
inline void poly_inv(ll* a,ll* b,int len)//倍增多项式求逆
{
    b[0]=po(a[0],mod-2);
    for(int k=1,j=0;k<=len;k<<=1,j++)
    {
        for(int i=1;i<(k<<1);i++)rv[i]=(rv[i>>1]>>1)|((i&1)<<j);
        for(int i=0;i<k;i++)tr1[i]=a[i];for(int i=0;i<k;i++)tr2[i]=b[i];
        ntt(tr1,0,k<<1);ntt(tr2,0,k<<1);
        for(int i=0;i<(k<<1);i++)b[i]=tr2[i]*(2+mod-tr1[i]*tr2[i]%mod)%mod;
        ntt(b,1,k<<1);for(int i=k;i<(k<<1);i++)b[i]=0;
    }
}
int main()
{
    for(int k=2,j=1;j<=18;k<<=1,j++)rt[0][j]=po(3,(mod-1)/k);
    for(int k=2,j=1;j<=18;k<<=1,j++)rt[1][j]=po(332748118,(mod-1)/k);
    scanf("%d",&n);for(int i=1;i<n;i++)scanf("%lld",&g[i]);
    for(Len=1;Len<n;Len<<=1);for(int i=1;i<n;i++)g[i]=mod-g[i];(g[0]+=1)%=mod;//处理出要求逆的多项式
    poly_inv(g,ig,Len);
    for(int i=0;i<n;i++)printf("%lld ",ig[i]);printf("\n");return 0;
}

评论

  • 还没有评论
作者: a2956331800 更新时间: 2019-01-05 21:49  在Ta的博客查看 举报    5  

生成函数

$$f[i]=\sum_{j=1}^if[i-j]*g[j],i>0$$

设$f(x)=\sum\limits_{i=0}^\infty f[i]x^i,g(x)=\sum\limits_{i=0}^\infty g[i]x^i$(设$g[0]=0$)

发现把$f$和$g$卷积后$f$常数项没有了:

$$f(x)*g(x)=\sum_{i=0}^\infty\sum_{j=0}^\infty f[i]\times g[j]x^{i+j}$$

令$k=i+j$

$$f(x)*g(x)=\sum_{k=0}^\infty(\sum_{j=0}^kf[k-j]g[j])x^k$$

$k>0$时$\sum_{j=0}^kf[k-j]g[j]=f[k]$

$k=0$时$\sum_{j=0}^kf[k-j]g[j]=0$($g[0]=0$)

所以$f(x)*g(x)=\sum\limits_{k=1}^\infty f[k]x^k$,和$f(x)$对比一下发现就差了一个常数项

即$f(x)*g(x)+f[0]=f(x)$

然后用初中数学知识(就是把未知数换成了多项式)就能算出来

$$f(x)=\frac{f[0]}{1-g(x)}$$

多项式求逆就完了

生成函数真是人类智慧做法

代码(是个正在完善的多项式板子,什么$\ln \exp$都有可以拿去看)

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#define md 998244353LL
#define inv(x) power(x,md-2)
#define max_n 1000000
using namespace std;

int n,N,i;

long long num[max_n],ans[max_n];

//const double pi=acos(-1);
//
//struct complex
//{
//  double x,y;
//  complex operator +(complex a)
//  {
//      return (complex){x+a.x,y+a.y};
//  }
//  complex operator -(complex a)
//  {
//      return (complex){x-a.x,y-a.y};
//  }
//  complex operator *(complex a)
//  {
//      return (complex){x*a.x-y*a.y,x*a.y+y*a.x};
//  }
//  complex operator /(double a)
//  {
//      return (complex){x/a,y/a};
//  }
//};

long long power(long long a,long long n)
{
    long long ans=1;
    while(n)
    {
        if(n&1)
          ans=ans*a%md;
        a=a*a%md;
        n>>=1;
    }
    return ans;
}

int re[max_n];
void build_re(int N)
{
    int x,now=N>>1,len=0;
    while(now)
      len++,now>>=1;
    for(int i=0;i<N;i++)
    {
        x=i;now=0;
        for(int j=0;j<len;j++)
          now=(now<<1)|(x&1),x>>=1;
        re[i]=now;
    }
}

//void FFT(complex a[],int len,int opt)
//{
//  for(int i=0;i<len;i++)
//    if(i<re[i])
//      swap(a[i],a[re[i]]);
//  complex wn,w,x;
//  for(int i=2;i<=len;i<<=1)
//    for(int j=(wn=(complex){cos(pi*2/i),opt*sin(pi*2/i)},0);j<len;j+=i)
//      for(int k=(w=(complex){1,0},0);k<i>>1;k++,w=w*wn)
//        x=w*a[j+k+(i>>1)],a[j+k+(i>>1)]=a[j+k]-x,a[j+k]=a[j+k]+x;
//  if(opt==-1)
//    for(int i=0;i<len;i++)
//      a[i]=a[i]/len;
//}
void NTT(long long a[],int len,int opt)
{
    for(int i=0;i<len;i++)
      if(i<re[i])
        swap(a[i],a[re[i]]);
    long long wn,w,x;
    for(int i=2;i<=len;i<<=1)
      for(int j=(wn=power(3,(md-1)/i),(opt==-1?wn=power(wn,md-2):0),0);j<len;j+=i)
        for(int k=(w=1,0);k<i>>1;k++,w=w*wn%md)
          x=a[j+k+(i>>1)]*w%md,a[j+k+(i>>1)]=(a[j+k]-x+md)%md,a[j+k]=(a[j+k]+x)%md;
    if(opt==-1)
    {
        long long inv=power(len,md-2);
        for(int i=0;i<len;i++)
          a[i]=a[i]*inv%md;
    }
}
//void poly_mul(long long a[],long long b[],long long tar[],int len)
//{
//  static long long A[4*max_n],B[4*max_n];
//  memcpy(A,a,sizeof(long long)*len);memcpy(B,b,sizeof(long long)*len);
//  build_re(len);
//  NTT(A,len,1);NTT(B,len,1);
//  for(int i=0;i<len;i++)
//    tar[i]=A[i]*B[i]%md;
//  NTT(tar,len,-1);
//}
void poly_inv(long long a[],long long tar[],int len)
{
    static long long now[4*max_n],ret[4*max_n];
    memset(now,0,sizeof(long long)*len);memset(ret,0,sizeof(long long)*len);
    ret[0]=inv(a[0]);
    for(int i=2;i<=len;i<<=1)
    {
        build_re(i<<1);
        memcpy(now,a,sizeof(long long)*i);
        NTT(ret,i<<1,1);NTT(now,i<<1,1);
        for(int j=0;j<i<<1;j++)
          ret[j]=ret[j]*(2LL-now[j]*ret[j]%md+md)%md;
        NTT(ret,i<<1,-1);
        memset(ret+i,0,sizeof(long long)*i);
    }
    memcpy(tar,ret,sizeof(long long)*len);
}
//void poly_dir(long long a[],long long tar[],int len)
//{
//  for(int i=0;i<len-1;i++)
//    tar[i]=a[i+1]*(i+1)%md;
//}
//void poly_int(long long a[],long long tar[],int len)
//{
//  for(int i=len;i>=1;i--)
//    tar[i]=a[i-1]*inv(i)%md;
//  tar[0]=0;
//}
//void poly_ln(long long a[],long long tar[],int len)
//{
//  static long long now[4*max_n],ret[4*max_n];
//  memset(now,0,sizeof(long long)*len);memset(ret,0,sizeof(long long)*len);
//  poly_inv(a,ret,len);
//  poly_dir(a,now,len);
//  poly_mul(now,ret,ret,len<<1);
//  poly_int(ret,ret,len);
//  memcpy(tar,ret,sizeof(long long)*len);
//}
//void poly_exp(long long a[],long long tar[],int len)
//{
//  static long long now[4*max_n],ret[4*max_n],ln[4*max_n];
//  memset(now,0,sizeof(long long)*len);memset(ret,0,sizeof(long long)*len);memset(ln,0,sizeof(long long)*len);
//  ret[0]=1;
//  for(int i=2;i<=len;i<<=1)
//  {
//      poly_ln(ret,now,i);
//      for(int j=0;j<i;j++)
//        now[j]=(a[j]-now[j]+(j==0)+md)%md;
//      poly_mul(now,ret,ret,i<<1);
//  }
//  memcpy(tar,ret,sizeof(long long)*len);
//}

char Getchar()
{
    return getchar();
    static char buff[1000000],*p,*end=p;
    if(p==end)
      end=buff+fread(p=buff,1,1000000,stdin);
    return *(p++);
}
template<typename T>void read(T &x)
{
    static char rc;
    x=0;rc=Getchar();
    while(!isdigit(rc))
      rc=Getchar();
    while(isdigit(rc))
      x=x*10+rc-'0',rc=Getchar();
}

int main()
{
    read(n);num[0]=1;
    for(i=1;i<n;i++)
      read(num[i]),num[i]=-num[i];
    N=1;
    while(N<n)
      N<<=1;
    poly_inv(num,ans,N);
    for(i=0;i<n;i++)
      cout<<ans[i]<<' ';
    return 0;
}
 
反馈
如果你认为某个题解有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。