2018-05-11 18:37:51

[TOC]

## 1.多项式乘法

#### 代码:


inline void FFT(comp*F,int tl)
{
rep(i,0,Len)if(i<rev[i])swap(F[rev[i]],F[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)
{
comp x=F[j+k+ii]*g[t][k];
F[j+k+ii]=F[j+k]-x;
F[j+k]=F[j+k]+x;
}
if(tl==-1)
{
reverse(F+1,F+Len);
rep(i,0,Len)F[i]=F[i]/Len;
}
}

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;
}
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;
}
}

int X[MAXN],Y[MAXN];

inline void mul(int *a,int *b,int *c,int lenl,int lenr)
{
if(lenl<=300/lenr)
{
Rep(i,0,lenl+lenr)c[i]=0;
Rep(i,0,lenl)Rep(j,0,lenr)c[i+j]=(c[i+j]+a[i]*b[j])%mod;
return;
}
for(Len=2;Len<=lenl+lenr;Len<<=1);
Rep(i,0,lenl)X[i]=a[i];
Rep(i,0,lenr)Y[i]=b[i];
rep(i,lenl+1,Len)X[i]=0;
rep(i,lenr+1,Len)Y[i]=0;
NTT(X,1),NTT(Y,1);
rep(i,0,Len)X[i]=(ll)X[i]*Y[i]%mod;
NTT(X,-1);
Rep(i,0,lenl+lenr)c[i]=X[i];
}

## 2.多项式求逆

#### 推导过程:

$f_i(x)\equiv F^{-1}(x)\pmod{x^{2^i}}$

$F(x)f_i(x)\equiv F(x)f_{i+1}(x)\pmod{x^{2^i}}$

$[f_i(x)-f_{i+1}(x)]\equiv 0\pmod{x^{2^i}}$

$[f_i(x)-f_{i+1}(x)]^2\equiv 0\pmod{x^{2^{i+1}}}$

$f_i^2(x)-2f_i(x)f_{i+1}(x)+f_{i+1}^2(x)\equiv 0\pmod{x^{2^{i+1}}}$

$f_{i+1}(x)-2f_i(x)+F(x)f_i^2(x)\equiv 0\pmod{x^{2^{i+1}}}$

$f_{i+1}(x)\equiv 2f_i(x)-F(x)f_i^2(x)\pmod{x^{2^{i+1}}}$

#### 代码:


inline void Inv(int*F,int*G,int ln)
{
Iv[0]=power(F[0],mod-2);
rep(i,0,ln)X[i]=Y[i]=0;
for(register int Ln=2;Ln<=ln;Ln<<=1)
{
rep(i,0,Ln)X[i]=F[i];
rep(i,0,(Ln>>1))Y[i]=Iv[i];
Len=Ln,calrev();
NTT(X,1),NTT(Y,1);
rep(i,0,Ln)X[i]=(uint64)X[i]*Y[i]%mod;
NTT(X,-1);
rep(i,0,(Ln>>1))X[i]=0;
NTT(X,1);
rep(i,0,Ln)X[i]=(uint64)X[i]*Y[i]%mod;
NTT(X,-1);
rep(i,(Ln>>1),Ln)Iv[i]=mod-X[i];
}
rep(i,0,ln)G[i]=Iv[i];
}


## 3.多项式除法

$F=QG+R$

#### 推导过程:

$F_R(x)=x^{Deg(F)}F(\frac{1}{x})$

$\because F(x)=G(x)Q(x)+R(x)$

$\therefore F(\frac{1}{x})=G(\frac{1}{x})Q(\frac{1}{x})+R(\frac{1}{x})$

$\therefore x^nF(\frac{1}{x})=x^nG(\frac{1}{x})Q(\frac{1}{x})+x^nR(\frac{1}{x})$

$\therefore x^nF(\frac{1}{x})=x^mG(\frac{1}{x})x^{n-m}Q(\frac{1}{x})+x^{n-m+1}*x^{m-1}R(\frac{1}{x})$

$\therefore F_R(x)=G_R(x)Q_R(x)+x^{n-m+1}*R_R(x)$

$\therefore F_R(x)=G_R(x)Q_R(x)\pmod{x^{n-m+1}}$

$\therefore Q_R(x)=F_R(x)G_R^{-1}(x)\pmod{x^{n-m+1}}$

#### 代码:

static int X[MAXN],Y[MAXN];

inline void Div(int *a,int n,int *b,int m)
{
memcpy(X,a,sizeof X);memcpy(Y,b,sizeof Y);
reverse(b,b+m+1);reverse(X,X+n+1);
Rep(i,n-m+1,n)X[i]=0;
Inv(b,n-m+1);
while(Len<=(n<<2))Len<<=1;
calrev(Len);
mul(X,b);reverse(X,X+n-m+1);
Rep(i,n-m+1,n)X[i]=0;
mul(Y,X);
memcpy(a,X,sizeof X);
}

## 4.多项式开方

$T_0^2-T^2\equiv 0\pmod{x^t}$

$(T_0+T)(T_0-T)\equiv 0\pmod{x^t}$

$T'^2-2T_T+T^2\equiv 0\pmod{x^{2t}}$

$T'^2-2TT_0+F\equiv 0\pmod{x^{2t}}$

$T\equiv \frac{T_0^2+F}{2T_0}\pmod{x^{2t}}$

#### 代码:

inline void Sqrt(int*F,int*G,int ln)
{
G[0]=1;
for(register int Ln=2;Ln<=ln;Ln<<=1)
{
mul(G,G,ExX,Ln>>1,Ln>>1);
rep(i,Ln>>1,Ln)ExX[i]=0;
Inv(G,ExY,Ln>>1);
Len=Ln,calrev();
NTT(ExX,1),NTT(ExY,1);
rep(i,0,Ln)ExX[i]=(ll)ExX[i]*ExY[i]%mod;
NTT(ExX,-1);
rep(i,0,Ln>>1)G[i+(Ln>>1)]=(ll)ExX[i]*inv2%mod;
}
}

## 5.多项式积分和求导

$\int F(x)=\sum\limits_{i=0}^n \frac{a_i}{i+1}x^{i+1}$

$\frac{dF}{dx}=\sum\limits_{i=1}^n ia_ix^{i-1}$

#### 代码:

inline void Direv(int *a,int n)
{Rep(i,1,n)a[i-1]=(ll)a[i]*i%mod;a[n]=0;}

inline void Inter(int *a,int n)
{Repe(i,n,1)a[i]=(ll)a[i-1]*power(i,mod-2)%mod;a[0]=0;}

## 6.多项式取 $\ln$

$\ln$ 的定义为 $\exp$ 的逆变换。具体定义请参考下面的 $\exp$ 。

$$\ln F=\int \frac{F'}{F}\equiv \int F'F^{-1}$$

#### 代码:

inline void Ln(int *a,int n)
{
memcpy(X,a,sizeof X);
Inv(X,n);Direv(a,n);
while(Len<=(n<<2))Len<<=1;
calrev(Len);
mul(a,X);
Inter(a,n);
Rep(i,n+1,Len)a[i]=0;
}

## 7.多项式牛顿迭代

$F(x)≡F_0(x)-\frac{G(F_0(x))}{G'(F_0(x))} \pmod {x^{2t}}$

### 7.1推导过程:

$$G(F)=G(F_0)+G'(F_0)(F-F_0)+G''(F_0)(F-F_0)^2+\cdots$$

$$G(F)=G(F_0)+G'(F_0)(F-F_0)$$

(代码依 $G$ 不同而不同)

### 7.2.其他式子利用牛顿迭代推导的方式

#### 7.2.1 求逆

$\delta(F)=GF-1$

$\delta'(F)=G$

$=F_0-\frac{G_0F_0-1}{G_0}$

$=F_0-F_0(G_0F_0-1)$

$=2F_0-G_0F_0^2$

#### 7.2.2 开方

$\delta(F)=F^2-G$

$\delta'(F)=2F$

$F=F_0-\frac{\delta(F_0)}{\delta'(F_0)}$$=F_0-\frac{F_0^2-G_0}{2F_0}$$=\frac{F_0^2+G_0}{2F_0}$

## 8.多项式 $\exp$

$G=G_0(1-\ln G_0+F)$

#### 代码:

static int ExX[MAXN],ExY[MAXN];

inline void Exp(int *F,int *G,int ln)
{
G[0]=1;
for(register int Lx=2;Lx<=ln;Lx<<=1)
{
rep(i,Lx>>1,Lx)G[i]=0;
Ln(G,ExX,Lx);
rep(i,0,Lx>>1)ExY[i]=G[i];
rep(i,Lx>>1,Lx)ExX[i]=0;
Len=Lx;
calrev();
NTT(ExY,1),NTT(ExX,1);
rep(i,0,Len)ExX[i]=(ll)ExX[i]*ExY[i]%mod;
NTT(ExX,-1);
rep(i,0,Len>>1)G[i+(Len>>1)]=ExX[i];
}
}

## 9.多项式幂次

$$F^k=\exp(k\ln F)$$

$$F^k=a_t^kx^{tk}\exp(k\ln \frac{F}{a_tx^t})$$

#### 代码:

inline void Pow(int*F,int*G,int ln,ll k)
{
int lst=ln+1;
Rep(i,0,ln)if(F[i]){lst=i;break;}
if(ln&&(__int128)lst*k>ln)
{memset(G,0,sizeof(int)*(ln+1));return;}
int md=ln-k*lst,bs=F[lst],iv=power(bs,mod-2);
Rep(i,lst,ln)G[i]=(ll)G[i]*iv%mod;
Ln(G+lst,G,md);
k%=mod;
Rep(i,0,md)G[i]=(ll)G[i]*k%mod;
Exp(G,G,md);
bs=power(bs,k);
Repe(i,md,0)G[i+lst*k]=(ll)G[i]*bs%mod;
memset(G,0,sizeof(int)*(lst*k));
}

### 9.5.多项式 $k$ 次方根

$$\sqrt[k]F=F^{\frac{1}{k}}=F^{k^{-1}}$$

## 10.拉格朗日反演

$$[x^n] F(x)=\frac{1}{n}[x^{n-1}](\frac{x}{G(x)})^n$$

#### 代码:

inline int Lagrange(int *a,int n)
{
Rep(i,0,n-1)a[i]=a[i+1];
Inv(a,n);
pow(a,n,n);
return (ll)a[n-1]*power(n,mod-2)%mod;
}

### 10.5 扩展拉格朗日反演

$$[x^n]H[F(x)]=\frac{1}{n}[x^{n-1}]H'(x)(\frac{x}{G(x)})^n$$

## 11.分治FFT

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

void cdq_FFT(int l,int r)
{
if(l==r)
{
if(!l)F[l]=1;
else F[l]=(ll)F[l]*iv[l]%mod;
return;
}
int md=(l+r)>>1;cdq_FFT(l,md);
for(Len=2;Len<=r-l;Len<<=1);
calrev();
memset(X,0,sizeof(int)*Len);
memset(Y,0,sizeof(int)*Len);
memcpy(X,F+l,sizeof(int)*(md-l+1));
memcpy(Y,a,sizeof(int)*(r-l));
NTT(X,1),NTT(Y,1);
rep(i,0,Len)X[i]=(ll)X[i]*Y[i]%mod;
NTT(X,-1);
cdq_FFT(md+1,r);
}

### 11.5.特殊的分治FFT

void cdqFFT(int *f,int l,int r)
{
if(l==r)
{
return;
}
int mid=(l+r)>>1;
cdqFFT(f,l,mid);
for(Len=r-l+1;Len>(Len&-Len);Len+=(Len&-Len));
Rep(i,0,Len)A[i]=B[i]=0;
Rep(i,l,mid)A[i-l]=(uint64)f[i]*(i-1)%mod,B[i-l]=f[i];
calrev(Len);mul(A,B);
if(l^2)
{
Rep(i,0,Len)A[i]=B[i]=0;
Rep(i,2,min(l-1,r-l))A[i-2]=f[i];
Rep(i,l,mid)B[i-l]=f[i];
mul(A,B);
Rep(i,mid+1,r)if(i>=l+2)
}
cdqFFT(f,mid+1,r);
}

1. 所计算区间左端点是全局左端点。原来怎么做就怎么做。但是注意不要在卷积中用到还没有计算完毕的项。
2. 所计算区间不是全局左端点。可以知道会存在一些项之前并没有计算过。我们将这些项合并一起计算。具体来说就是把 $(i-1)f_if_{n-i}$ 和 $(n-i-1)f_{n-i}f_i$ 一起计算。那么这两项加在一起就变成了$(n-2)f_if_{n-i}$ 。直接加上即可。

## 13.多项式求三角函数

$$e^{w_4x}=\cos(x)+w_4\sin(x)$$

$$e^{w_4F(x)}=\cos[F(x)]+w_4\sin[F(x)]$$

$$\cos(x)=\sum_{i=0}^\infty \frac{[i\bmod 2=0](-1)^\frac{i}{2}x^i}{i!}$$

$$\cosh(x)=\frac{e^x+e^{-x}}{2}=\sum_{i=0}^\infty \frac{[i\bmod 2=0]x^i}{i!}$$

$$\cos(x)=\frac{e^{w_4x}+e^{-w_4x}}{2}$$

$$\cos(F)=\frac{1}{2}(e^{w_4F}-e^{-w_4F})$$

$$\sin(x)=\sum_{i=0}^\infty \frac{[i\bmod2=1](-1)^{\frac{i-1}{2}}x^i}{i!}$$

$$\sinh(x)=\frac{e^x-e^{-x}}{2}=\sum_{i=0}^\infty \frac{[i\bmod2=1]x^i}{i!}$$

$$\sin(x)=\frac{w_4^3}{2}(e^{w_4x}-e^{-w_4x})$$

$$\sin F=\frac{w_4^3}{2}(e^{w_4F}-e^{-w_4F})$$

#### 代码:

static int Sn[MAXN],Cs[MAXN];

inline void Cos(int*F,int*G,int ln)
{
Rep(i,0,ln)Cs[i]=(ll)F[i]*w4%mod;
Exp(Cs,Cs,ln),Inv(Cs,G,ln);
Rep(i,0,ln)G[i]=((ll)Cs[i]+G[i])*inv2%mod;
}

const int w43div2=(ll)w4*w4%mod*w4%mod*inv2%mod;

inline void Sin(int*F,int*G,int ln)
{
Rep(i,0,ln)Sn[i]=(ll)F[i]*w4%mod;
Exp(Sn,Sn,ln),Inv(Sn,G,ln);
Rep(i,0,ln)G[i]=((ll)Sn[i]+mod-G[i])*w43div2%mod;
}

## 14.多项式反三角函数

$$\arcsin x = \int \frac{1}{\sqrt{1-x^2}}$$

$$\arctan x = \int \frac{1}{1+x^2}$$

$$\arcsin F = \int \frac{F'}{\sqrt{1-F^2}}$$

$$\arctan F = \int \frac{F'}{1+F^2}$$

inline void Arcsin(int*F,int*G,int ln)
{
memcpy(Sn,F,sizeof(int)*(ln+1));
for(Len=2;Len<=ln*2;Len<<=1);calrev();
NTT(Sn,1);rep(i,0,Len)Sn[i]=(ll)Sn[i]*Sn[i]%mod;
NTT(Sn,-1);
Sn[0]=1;rep(i,ln+1,Len)Sn[i]=0;
Rep(i,1,ln)Sn[i]=mod-Sn[i];
Sqrt(Sn,Sn,ln);
Inv(Sn,Sn,ln);
Deriv(F,G,ln);
mul(G,Sn,G,ln,ln);
Rep(i,ln+1,ln<<1)G[i]=0;
Inter(G,G,ln);
}

inline void Arctan(int*F,int*G,int ln)
{
memcpy(Sn,F,sizeof(int)*(ln+1));
for(Len=2;Len<=ln*2;Len<<=1);calrev();
NTT(Sn,1);rep(i,0,Len)Sn[i]=(ll)Sn[i]*Sn[i]%mod;
NTT(Sn,-1),Sn[0]=1;
rep(i,ln+1,Len)Sn[i]=0;Inv(Sn,Sn,ln);
Deriv(F,G,ln),mul(G,Sn,G,ln,ln);
Rep(i,ln+1,ln<<1)G[i]=0;
Inter(G,G,ln);
}

## 15.多项式多点求值

$$F_{l,mid}(x)=F_{l,r}(x)\bmod D_{l,mid}(x)$$

#### 代码:

static int solv[18][2][MAXN];

inline void calc(int*a,int l,int r,int lev,int dir)
{
if(l==r)
{
solv[lev][dir][0]=mod-a[l];
solv[lev][dir][1]=1;return;
}
int md=(l+r)>>1;
calc(a,l,md,lev+1,0),calc(a,md+1,r,lev+1,1);
mul(solv[lev+1][0],solv[lev+1][1],solv[lev][dir],md-l+1,r-md);
}

static int pol[18][MAXN],Q[MAXN];

void getnum(int*a,int*ans,int l,int r,int lev,int n)
{
if(n>r-l)
{
calc(a,l,r,0,0);
Div(pol[lev-(lev>0)],solv[0][0],Q,pol[lev],n,r-l+1);
n=r-l;
}
else if(lev){Rep(i,0,n)pol[lev][i]=pol[lev-1][i];}
if(l==r)
{
ans[l]=pol[lev][0];
return;
}
int md=(l+r)>>1;
getnum(a,ans,l,md,lev+1,n);
getnum(a,ans,md+1,r,lev+1,n);
}

## Ex1.MTT

inline void mul(int*F,int*G)
{
rep(i,0,Len)A[i]=comp(F[i]>>15,F[i]&32767),
C[i]=comp(G[i]>>15,G[i]&32767);
DBLFFT(A,B,1),DBLFFT(C,D,1);
rep(i,0,Len)
{
register comp t=A[i];
A[i]=B[i]*C[i]+A[i]*D[i];
B[i]=B[i]*D[i];
C[i]=C[i]*t;
}
DBLFFT(A,B,-1),FFT(C,-1);
rep(i,0,Len)
{
register int lz=(((ll)floor(C[i].re+0.5))%mod*73741817
+((ll)floor(A[i].re+0.5))%mod*32768+(ll)floor(B[i].re+0.5))%mod;
F[i]=i<=k?lz:0;
}
}

## Ex2.BlueStein算法

$$F(w_k^t)=\sum_{i=0}^{k-1}f_iw_k^{ti}$$

$$=\sum_{i=0}^{k-1}f_iw_k^{-(k-t)i}$$

$$ti=\binom{t+i}{2}-\binom{t}{2}-\binom{i}{2}$$

$$ans_t=\sum_{i=0}^{k-1} f_iw_k^{\binom{i-t}{2}-\binom{-t}{2}-\binom{i}{2}}$$

$$=w_k^{-\binom{-t}{2}}\sum_{i=0}^{k-1} f_iw_k^{-\binom{i}{2}}*w_k^{\binom{-(t-i)}{2}}$$

$$ans_t=w_k^{-\binom{-t}{2}}\sum_{i=0}^{k-1+t} f_iw_k^{-\binom{i}{2}}*w_k^{\binom{k-1-(k-1+t-i)}{2}}$$

$$ans_t=w_k^{-\binom{-t}{2}}[k-1+t](A*B)$$

inline void Blue_Stein(int*F,int*G,int ln)
{
rep(i,0,ln)A[i]=(ll)F[i]*power(ome,ln-(ll)i*(i-1)/2%ln,mod)%mod;
Rep(i,0,2*ln-2)B[i]=power(ome,ln+(ll)(ln-1-i)*(ln-2-i)/2%ln,mod);
mul(A,B,A,ln-1,2*ln-2);
reverse(A+1,A+k);
rep(i,0,ln)G[i]=(ll)A[i+k-1]*power(ome,ln-(ll)(-i)*(-i-1)/2%ln,mod)%mod;
}

## Ex3.常数优化


static comp Z[MAXN];

inline void DBLFFT(comp*F,comp*G,int tl)
{
if(tl==1)
{
memcpy(Z,F,sizeof(comp)*Len);
FFT(Z,1);
memcpy(F,Z,sizeof(comp)*Len);
reverse(F+1,F+Len);
rep(i,0,Len)F[i].im=-F[i].im;
rep(i,0,Len)G[i]=(Z[i]-F[i])/2,F[i]=(Z[i]+F[i])/2
,swap(G[i].re,G[i].im),G[i].im=-G[i].im;
}
else
{
rep(i,0,Len)F[i]=comp(F[i].re-G[i].im,F[i].im+G[i].re);
FFT(F,-1);
rep(i,0,Len)G[i]=comp(F[i].im,0),F[i]=comp(F[i].re,0);
}
}

## 总集:帕秋莉的超级多项式

$$\left[\left(1+\ln(1+\frac{1}{\exp(\int\frac{1}{\sqrt{F}})})\right)^k\right]'$$

#### 代码:

#include<bits/stdc++.h>
#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()
{
}
static char Out[Output],*nowps=Out;

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

{
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(void)
{
FILE*DSD=freopen("polynomial.in","r",stdin);
FILE*CSC=freopen("polynomial.out","w",stdout);
}

const int MAXN=1<<21;

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

static int g[23],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,21)g[i]=power(gen,(mod-1)>>i);
iv[1]=1;
Rep(i,2,1e5)iv[i]=mod-(uint64)mod/i*iv[mod%i]%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 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)
{
register int wn=*(g+t);
for(register int j=0;j<Len;j+=i)
{
register int w=1;
rep(k,0,ii)
{
register int tt=(uint64)*(F+j+k+ii)*w%mod;
w=(uint64)w*wn%mod;
}
}
}
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;
}
}

static int X[MAXN],Y[MAXN],Iv[MAXN];

inline void mul(int *a,int *b,int *c,int lenl,int lenr)
{
if((ll)lenl*lenr<=300)
{
Rep(i,0,lenl+lenr)X[i]=0;
Rep(i,0,lenl)Rep(j,0,lenr)
X[i+j]=(X[i+j]+(ll)a[i]*b[j])%mod;
Rep(i,0,lenl+lenr)c[i]=X[i];
return;
}
for(Len=2;Len<=lenl+lenr;Len<<=1);
calrev();
Rep(i,0,lenl)X[i]=a[i];
Rep(i,0,lenr)Y[i]=b[i];
rep(i,lenl+1,Len)X[i]=0;
rep(i,lenr+1,Len)Y[i]=0;
NTT(X,1),NTT(Y,1);
rep(i,0,Len)X[i]=(ll)X[i]*Y[i]%mod;
NTT(X,-1);
Rep(i,0,lenl+lenr)c[i]=X[i];
rep(i,lenl+lenr+1,Len)c[i]=0;
}

inline void Inv(int*F,int*G,int ln)
{
Iv[0]=power(F[0],mod-2);
for(register int Ln=2;Ln>>1<=ln;Ln<<=1)
{
rep(i,ln+1,Ln)F[i]=0;
rep(i,0,Ln)X[i]=F[i],Y[i]=0;
rep(i,0,(Ln>>1))Y[i]=Iv[i];
Len=Ln,calrev();
NTT(X,1),NTT(Y,1);
rep(i,0,Ln)X[i]=(uint64)X[i]*Y[i]%mod;
NTT(X,-1);
rep(i,0,(Ln>>1))X[i]=0;
NTT(X,1);
rep(i,0,Ln)X[i]=(uint64)X[i]*Y[i]%mod;
NTT(X,-1);
rep(i,(Ln>>1),Ln)Iv[i]=mod-X[i];
}
Rep(i,0,ln)G[i]=Iv[i];
}

static int ExX[MAXN],ExY[MAXN],Op[MAXN];

inline void Div(int*F,int*G,int*Q,int*R,int lenf,int leng)
{
Rep(i,0,lenf)ExX[i]=F[lenf-i];
Rep(i,0,leng)ExY[i]=G[leng-i];
Rep(i,leng+1,lenf-leng)ExY[i]=0;
Inv(ExY,ExY,lenf-leng);
Rep(i,lenf-leng+1,lenf)ExX[i]=0;
Rep(i,lenf-leng+1,leng)ExY[i]=0;
mul(ExX,ExY,ExY,lenf-leng,lenf-leng);
Rep(i,lenf-leng+1,(lenf-leng)<<1)ExY[i]=0;
Rep(i,0,(lenf-leng)>>1)swap(ExY[i],ExY[lenf-leng-i]);
mul(ExY,G,ExX,lenf-leng,leng);
assert(F[leng]==ExX[leng]);
Rep(i,0,lenf-leng)Q[i]=ExY[i];
}

const int inv2=(mod+1)>>1;

inline void Sqrt(int*F,int*G,int ln)
{
Op[0]=sqrt(F[0]);
for(register int Ln=2;Ln>>1<=ln;Ln<<=1)
{
mul(Op,Op,ExX,Ln>>1,Ln>>1);
rep(i,Ln>>1,Ln)Op[i]=ExX[i]=0;
Inv(Op,ExY,Ln>>1);
Len=Ln,calrev();
NTT(ExX,1),NTT(ExY,1);
rep(i,0,Ln)ExX[i]=(ll)ExX[i]*ExY[i]%mod;
NTT(ExX,-1);
rep(i,0,Ln>>1)Op[i+(Ln>>1)]=(ll)ExX[i]*inv2%mod;
}
Rep(i,0,ln)G[i]=Op[i];
}

inline void Deriv(int*F,int*G,int ln)
{Rep(i,1,ln)G[i-1]=(uint64)F[i]*i%mod;G[ln]=0;}

inline void Inter(int*F,int*G,int ln)
{Repe(i,ln,1)G[i]=(uint64)F[i-1]*iv[i]%mod;G[0]=0;}

static int LnX[MAXN];

inline void Ln(int*F,int*G,int ln)
{
Deriv(F,LnX,ln),Inv(F,G,ln);
for(Len=2;Len<=ln<<1;Len<<=1);
rep(i,ln+1,Len)LnX[i]=G[i]=0;
calrev();
NTT(LnX,1),NTT(G,1);
rep(i,0,Len)G[i]=(uint64)G[i]*LnX[i]%mod;
NTT(G,-1);
Inter(G,G,ln);
}

inline void Exp(int *F,int *G,int ln)
{
Op[0]=1;
for(register int Lx=2;Lx>>1<=ln;Lx<<=1)
{
rep(i,Lx>>1,Lx)Op[i]=0;
Ln(Op,ExX,Lx);
rep(i,0,Lx>>1)ExY[i]=Op[i];
rep(i,Lx>>1,Lx)ExX[i]=ExY[i]=0;
Len=Lx;
calrev();
NTT(ExY,1),NTT(ExX,1);
rep(i,0,Len)ExX[i]=(ll)ExX[i]*ExY[i]%mod;
NTT(ExX,-1);
rep(i,0,Lx>>1)Op[i+(Len>>1)]=ExX[i];
}
Rep(i,0,ln)G[i]=Op[i];
}
}
using poly::power;
using poly::Len;
using poly::calrev;
using poly::NTT;
using poly::mod;
using poly::predone;
using poly::Inv;
using poly::Inter;
using poly::Deriv;
using poly::Ln;
using poly::Exp;
using poly::Sqrt;
using poly::Div;

static int n,k,F[MAXN];

int main()
{
file();
predone();
k%=mod;
Sqrt(F,F,n-1);
Inv(F,F,n-1);
Inter(F,F,n-1);
Exp(F,F,n-1);
Inv(F,F,n-1);
++F[0];
Ln(F,F,n-1);
++F[0];
Ln(F,F,n-1);
Rep(i,0,n-1)F[i]=(ll)F[i]*k%mod;
Exp(F,F,n-1);
Deriv(F,F,n-1);
Rep(i,0,n-1)write(F[i],' ');
flush();
return 0;
}

• star
首页