多项式十九连
xenonex
2018-11-28 13:13:39
P3803 [【模板】多项式乘法（FFT）](https://www.luogu.org/problemnew/show/P3803)
P1919 [【模板】A*B Problem升级版（FFT快速傅里叶）](https://www.luogu.org/problemnew/show/P1919)
P4245 [【模板】任意模数NTT](https://www.luogu.org/problemnew/show/P4245)
P4238 [【模板】多项式求逆](https://www.luogu.org/problemnew/show/P4238)
P4239 [【模板】多项式求逆（加强版）](https://www.luogu.org/problemnew/show/P4239)
P4721 [【模板】分治 FFT](https://www.luogu.org/problemnew/show/P4721)
P4512 [【模板】多项式除法](https://www.luogu.org/problemnew/show/P4512)
P4723 [【模板】线性递推](https://www.luogu.org/problemnew/show/P4723)
P4725 [【模板】多项式对数函数](https://www.luogu.org/problemnew/show/P4725)
P4726 [【模板】多项式指数函数](https://www.luogu.org/problemnew/show/P4726)
P5205 [【模板】多项式开根](https://www.luogu.org/problemnew/show/P5205)
P5277 [【模板】多项式开根（加强版）](https://www.luogu.org/problemnew/show/P5277)
P5245 [【模板】多项式快速幂](https://www.luogu.org/problemnew/show/P5245)
P5273 [【模板】多项式幂函数（加强版）](https://www.luogu.org/problemnew/show/P5273)
P5264 [【模板】多项式三角函数](https://www.luogu.org/problemnew/show/P5264)
P5265 [【模板】多项式反三角函数](https://www.luogu.org/problemnew/show/P5265)
P5050 [【模板】多项式多点求值](https://www.luogu.org/problemnew/show/P5050)
P5158 [【模板】多项式快速插值](https://www.luogu.org/problemnew/show/P5158)
P5282 [【模板】快速阶乘算法](https://www.luogu.org/problemnew/show/P5282)
奇怪的板子
```cpp
#include<cstdio>
#include<cstring>
#define L 262144
#define mod 998244353
typedef long long LL;
typedef unsigned long long ULL;
int rev[L<<1],W[L],_i[19],inv[L];
int pool[5242880],*ptr,*src,*dst,*pi[L],cpitmp[L],*mou[18],intmp[L];
inline int invx(int x){int r=1;for(x%=mod;x>1;x=mod%x)r=LL(mod-mod/x)*r%mod;return r;}
inline int ksm(LL a,LL b){int r=1;for(;b;a=a*a%mod,b>>=1)if(b&1)r=r*a%mod;return r;}
void NTT_Init()
{
int i,j,t;
const int G = 3,i2 = invx(2),l = L>>1;
for(i=j=1;j<L;j<<=1)for(;i<j<<1;i++)rev[i<<1]=rev[i],rev[i<<1|1]=rev[i]|j;
t = ksm(G,mod/L), W[l] = 1;
for(i=1;i<l;i++)W[i+l] = (LL)W[i+l-1]*t%mod;
for(i=l-1;i;i--)W[i] = W[i<<1];
for(_i[0]=i=1;i<19;i++)_i[i] = (LL)_i[i-1]*i2%mod;
for(inv[1]=1,i=2;i<L;i++)inv[i] = LL(mod-mod/i)*inv[mod%i]%mod;
}
void NTT(int *a,int len,int sign)
{
static ULL f[L];
int h,i,j,k,*w,t; ULL *p,*q;
for(w=rev+len,i=0;i<len;i++)f[*w++] = a[i];
for(h=0,i=1;i<len;h++,i<<=1)
{
if(h == 16)for(j=0;j<len;j++)f[j] %= mod;
for(j=0;j<len;j+=i,j+=i)for(w=W+i,q=(p=f+j)+i,k=0;k<i;k++,p++,q++)
t = *q**w++%mod, *q = *p+mod-t, *p += t;
}
if(sign < 0)for(a[0]=f[0]*(k=_i[h])%mod,i=1;i<len;i++)a[len-i]=f[i]*k%mod;
else for(i=0;i<len;i++)a[i] = f[i]%mod;
}
void poly_inv(int *a,int len,int *f)
{
static int invtmp[L];
int l,l2,i;len <<= 1;
memset(f,0,len<<2), memset(invtmp,0,len<<2);
for(f[0]=invx(a[0]),l=2,l2=4;l<len;l<<=1,l2<<=1)
{
memcpy(invtmp,a,l<<2), NTT(invtmp,l2,1), NTT(f,l2,1);
for(i=0;i<l2;i++)f[i] = f[i]*(2-(LL)invtmp[i]*f[i]%mod+mod)%mod;
NTT(f,l2,-1), memset(f+l,0,l<<2);
}
}
void poly_div(int *a,int lena,int *b,int lenb,int *f,int *g)
{
static int divtmp1[L],divtmp2[L];
int lenf = lena-lenb+1,l,i,j;
if(lena < lenb){memcpy(g,a,lena<<2);memset(g+lena,0,(lenb-lena-1)<<2);return;}
for(l=1;l<lenf;l<<=1);l <<= 1;
for(i=0;i<lenb;i++)divtmp1[lenb-i-1] = b[i];
j = lenb; if(j > lenf){j = lenf;}memset(divtmp1+j,0,(l-j)<<2);
for(poly_inv(divtmp1,l>>1,f),NTT(f,l,1),i=0;i<lena;i++)divtmp1[lena-i-1] = a[i];
j = lena; if(j > lenf){j = lenf;}memset(divtmp1+j,0,(l-j)<<2), NTT(divtmp1,l,1);
for(i=0;i<l;i++)f[i] = (LL)f[i]*divtmp1[i]%mod;
for(NTT(f,l,-1),i=0,j=lenf-1;i<j;i++,j--)l = f[i], f[i] = f[j], f[j] = l;
for(l=1;l<lena;l<<=1);
memcpy(divtmp1,f,lenf<<2), memset(divtmp1+lenf,0,(l-lenf)<<2), NTT(divtmp1,l,1);
memcpy(divtmp2,b,lenb<<2), memset(divtmp2+lenb,0,(l-lenb)<<2), NTT(divtmp2,l,1);
for(i=0;i<l;i++)divtmp1[i] = (LL)divtmp1[i]*divtmp2[i]%mod;
for(NTT(divtmp1,l,-1),i=0;i<lena;i++)if((g[i]=a[i]-divtmp1[i]) < 0)g[i] += mod;
}
void poly_sqrt(int *a,int len,int *f)
{
static int sqrtmp[L],sqrtmp2[L];
int l,l2,i;len <<= 1;
memset(f,0,len<<2), memset(sqrtmp2,0,len<<2);
for(f[0]=1,l=2,l2=4;l<len;l<<=1,l2<<=1)
{
poly_inv(f,l,sqrtmp), memcpy(sqrtmp2,a,l<<2);
NTT(sqrtmp,l2,1), NTT(sqrtmp2,l2,1);
for(i=0;i<l2;i++)sqrtmp[i] = (LL)sqrtmp[i]*sqrtmp2[i]%mod;
NTT(sqrtmp,l2,-1);
for(i=l>>1;i<l;i++)f[i] = sqrtmp[i]&1?(sqrtmp[i]+mod)>>1:sqrtmp[i]>>1;
}
}
void poly_ln(int *a,int len,int *f)
{
static int lntmp[L];
int i,l = len<<1;
for(poly_inv(a,len,lntmp),i=0;i<len;i++)f[i] = a[i+1]*LL(i+1)%mod;
memset(f+len-1,0,(len+1)<<2);
for(NTT(lntmp,l,1),NTT(f,l,1),i=0;i<l;i++)lntmp[i] = (LL)lntmp[i]*f[i]%mod;
NTT(lntmp,l,-1), memset(f+len,0,len<<2);
for(f[0]=0,i=1;i<len;i++)f[i] = (LL)inv[i]*lntmp[i-1]%mod;
}
void poly_exp(int *a,int len,int *f)
{
static int exptmp[L],exptmp2[L];
int l,l2,i;len <<= 1;
memset(f,0,len<<2), memset(exptmp2,0,len<<2);
for(f[0]=1,l=2,l2=4;l<len;l<<=1,l2<<=1)
{
memcpy(exptmp2,a,l<<2);
poly_ln(f,l,exptmp), NTT(f,l2,1), NTT(exptmp,l2,1), NTT(exptmp2,l2,1);
for(i=0;i<l2;i++)f[i] = f[i]*LL(1-exptmp[i]+mod+exptmp2[i])%mod;
NTT(f,l2,-1), memset(f+l,0,l<<2);
}
}
void poly_sincos(int *a,int len,int *fsin,int *fcos)
{
static int sctmp1[L],sctmp2[L],sctmp3[L];
int I,i;
for(I=W[3],i=0;i<len;i++)sctmp1[i] = (LL)a[i]*I%mod;
poly_exp(sctmp1,len,sctmp2), poly_inv(sctmp2,len,sctmp3);
if(fsin){for(I=invx(W[3]<<1),i=0;i<len;i++)
{fsin[i] = LL(sctmp2[i]-sctmp3[i]+mod)*I%mod;}memset(fsin+len,0,len<<2);}
if(fcos){for(I=invx(W[2]<<1),i=0;i<len;i++)
{fcos[i] = LL(sctmp2[i]+sctmp3[i])*I%mod;}memset(fcos+len,0,len<<2);}
}
void poly_asin(int *a,int len,int *f)
{
static int asintmp[L];
int l = len<<1,i;
memcpy(asintmp,a,len<<2), memset(asintmp+len,0,len<<2);
for(NTT(asintmp,l,1),i=0;i<l;i++)asintmp[i] = (LL)asintmp[i]*asintmp[i]%mod;
for(NTT(asintmp,l,-1),asintmp[0]=1,i=2;i<len;i++)asintmp[i] = mod-asintmp[i];
poly_sqrt(asintmp,len,f), poly_inv(f,len,asintmp);
for(i=1;i<len;i++)f[i-1] = (LL)a[i]*i%mod;
f[len-1] = 0, NTT(f,l,1), NTT(asintmp,l,1);
for(i=0;i<l;i++)asintmp[i] = (LL)f[i]*asintmp[i]%mod;
for(NTT(asintmp,l,-1),f[0]=0,i=1;i<len;i++)f[i] = (LL)asintmp[i-1]*inv[i]%mod;
memset(f+len,0,len<<2);
}
void poly_atan(int *a,int len,int *f)
{
static int atantmp[L];
int l = len<<1,i;
memcpy(atantmp,a,len<<2), memset(atantmp+len,0,len<<2);
for(NTT(atantmp,l,1),i=0;i<l;i++)atantmp[i] = (LL)atantmp[i]*atantmp[i]%mod;
NTT(atantmp,l,-1), atantmp[0] = 1;
poly_inv(atantmp,len,f), memcpy(atantmp,f,l<<2);
for(i=1;i<len;i++)f[i-1] = (LL)a[i]*i%mod;
f[len-1] = 0, NTT(f,l,1), NTT(atantmp,l,1);
for(i=0;i<l;i++)atantmp[i] = (LL)f[i]*atantmp[i]%mod;
for(NTT(atantmp,l,-1),f[0]=0,i=1;i<len;i++)f[i] = (LL)atantmp[i-1]*inv[i]%mod;
memset(f+len,0,len<<2);
}
void _calc_pi(int t,int l,int r,int siz)
{
pi[t] = ptr, ptr += siz;
if(l == r){pi[t][0] = mod-src[l], pi[t][1] = 1;return;}
int mid = (l+r)>>1,i,*p = pi[t],*q = cpitmp;
_calc_pi(t<<1,l,mid,siz>>1), _calc_pi(t<<1|1,mid+1,r,siz>>1);
memcpy(cpitmp,pi[t<<1],siz<<1), memset(cpitmp+(siz>>1),0,siz<<1), NTT(cpitmp,siz,1);
memcpy(pi[t],pi[t<<1|1],siz<<1), NTT(pi[t],siz,1);
for(i=0;i<siz;i++,p++,q++)*p = (LL)*p**q%mod;
NTT(pi[t],siz,-1);
}
void _calc_eval(int *f,int len,int t,int l,int r,int dep)
{
poly_div(f,len,pi[t],r-l+2,cpitmp,mou[dep]);
if(l == r){dst[l] = *mou[dep];return;}
int mid = (l+r)>>1;
_calc_eval(mou[dep],r-l+1,t<<1,l,mid,dep-1);
_calc_eval(mou[dep],r-l+1,t<<1|1,mid+1,r,dep-1);
}
void poly_eval(int *func,int len,int *pts,int cnt,int *res)
{
int lc,logc,i;
for(lc=1,logc=0;lc<cnt;lc<<=1,logc++);
memset(pool,0,(lc<<3)*(logc+1));
ptr = pool, src = pts, dst = res;
_calc_pi(1,0,cnt-1,lc<<1);
for(i=0;i<=logc;i++)mou[i] = ptr, ptr += 2<<i;
_calc_eval(func,len,1,0,cnt-1,logc);
}
void _calc_inte(int t,int l,int r,int *f,int dep)
{
if(l == r){*f = intmp[l];if(dep){f[1] = 0;}return;}
int mid = (l+r)>>1,le = 1<<dep,i;
_calc_inte(t<<1,l,mid,mou[dep],dep-1), _calc_inte(t<<1|1,mid+1,r,f,dep-1);
memcpy(cpitmp,mou[dep],le<<1), memset(cpitmp+(le>>1),0,le<<1), NTT(cpitmp,le,1);
memset(f+(le>>1),0,le<<1), NTT(f,le,1), NTT(pi[t<<1],le,1), NTT(pi[t<<1|1],le,1);
for(i=0;i<le;i++)f[i] = ((LL)cpitmp[i]*pi[t<<1|1][i]+(LL)f[i]*pi[t<<1][i])%mod;
NTT(f,le,-1);
}
void poly_inte(int *ptsx,int *ptsy,int cnt,int *f)
{
int lc,logc,i;
for(lc=1,logc=0;lc<cnt;lc<<=1,logc++);
memset(pool,0,(lc<<3)*(logc+1));
ptr = pool, src = ptsx, dst = intmp;
_calc_pi(1,0,cnt-1,lc<<1);
for(i=0;i<=logc;i++)mou[i] = ptr, ptr += 2<<i;
for(i=1;i<=cnt;i++)intmp[i-1] = (LL)pool[i]*i%mod;
_calc_eval(intmp,cnt,1,0,cnt-1,logc);
for(i=0;i<cnt;i++)intmp[i] = (LL)ptsy[i]*invx(intmp[i])%mod;
_calc_inte(1,0,cnt-1,f,logc);
}
int main()
{
NTT_Init();
return 0;
}
```