【COGS】2189. [HZOI 2015] 帕秋莉的超级多项式-牛顿迭代多项式全家

传送门:cogs2189

题解

无脑套模板。
这里推荐一篇很好的博客:
有关多项式处理的各种算法总结

代码

#include
using namespace std;
const int mod=998244353,g=3;
const int N=3e5+1000;
int n,K,iv[N],a[N],b[N],rv[N];template
inline void rd(T &x)
{char c=getchar();int f=0;x=0;while(!isdigit(c)) {if(c=='-') f=1;c=getchar();}while(isdigit(c)) {x=x*10+(c^48);c=getchar();}if(f) x=-x;
}inline void out(int x){if(x>9) out(x/10);putchar('0'+x%10);}inline int ad(int x,int y) {x+=y;if(x>=mod) x-=mod;return x;}
inline int dc(int x,int y) {x-=y;if(x<0) x+=mod;return x;}
inline int mul(int x,int y) {return 1ll*x*y%mod;}inline int fp(int x,int y)
{int re=1;for(;y;y>>=1,x=mul(x,x))if(y&1) re=mul(re,x);return re;
}inline void NTT(int *e,int ptr,int len)
{int i,j,k,ori,G,pd,ix,iy;G= ptr? g:iv[g];//int k!for(i=1;i<len;++i) if(ifor(i=1;i<len;i<<=1){ori=fp(G,(mod-1)/(i<<1));for(j=0;j<len;j+=(i<<1)){pd=1;for(k=0;kif(ptr) return;for(i=0;i<len;++i) e[i]=mul(e[i],iv[len]);
}inline void getinv(int n,int *a,int *b)
{if(n==1){b[0]=fp(a[0],mod-2);return;}getinv((n+1)>>1,a,b);int i,j,len=1,L=0;static int cont[N];for(;lenlen<<=1) L++;for(i=1;i<len;++i) rv[i]=((rv[i>>1]>>1)|((i&1)<<(L-1)));for(i=0;ifor(i=n;i<len;++i) cont[i]=0;NTT(cont,1,len);NTT(b,1,len);for(i=0;i<len;++i) b[i]=mul(b[i],dc(2,mul(cont[i],b[i])));NTT(b,0,len);for(i=n;i<len;++i) b[i]=0;
}inline void getsqrt(int n,int *a,int *b)
{if(n==1) {b[0]=sqrt(a[0]);return;}getsqrt((n+1)>>1,a,b);int i,j,L=0,len=1;for(;lenlen<<=1) L++;static int inv[N],tp[N];for(i=0;i<len;++i) inv[i]=0;getinv(n,b,inv);for(i=1;i<len;++i) rv[i]=((rv[i>>1]>>1)|((i&1)<<(L-1)));for(i=0;ifor(i=n;i<len;++i) tp[i]=0;NTT(inv,1,len);NTT(b,1,len); NTT(tp,1,len);for(i=0;i<len;++i) b[i]=mul(ad(mul(b[i],b[i]),tp[i]),mul(iv[2],inv[i]));NTT(b,0,len);for(i=n;i<len;++i) b[i]=0;
}inline void getintegration(int n,int *a,int *b)
{for(int i=1;i-1],iv[i]);b[0]=0;
}inline void getderivative(int n,int *a,int *b)
{for(int i=0;i+1],i+1);b[n]=0;
}inline void getln(int n,int *a,int *b)
{int i,j,len=1,L=0;for(;lenlen<<=1) L++;static int der[N],nv[N];for(i=0;i<len;++i) der[i]=nv[i]=0;getderivative(n,a,der);getinv(n,a,nv);for(i=1;i<len;++i) rv[i]=((rv[i>>1]>>1)|(i&1)<<(L-1));NTT(nv,1,len);NTT(der,1,len);for(i=0;i<len;++i) der[i]=mul(der[i],nv[i]);NTT(der,0,len);getintegration(n,der,b);
}inline void getexp(int n,int *a,int *b)
{if(n==1) {b[0]=1;return;}getexp((n+1)>>1,a,b);int i,j,L=0,len=1;for(;lenlen<<=1) L++;static int ln[N];for(i=0;i<len;++i) ln[i]=0;getln(n,b,ln); for(i=0;i[0]=ad(ln[0],1);NTT(ln,1,len);NTT(b,1,len);for(i=0;i<len;++i) b[i]=mul(b[i],ln[i]); NTT(b,0,len);for(i=n;i<len;++i) b[i]=0;
}inline void getpow(int n,int *a,int *b,int K)
{int i,j,L=0,len=1;getln(n,a,b);for(;lenlen<<=1) L++;for(i=0;i<len;++i) b[i]=mul(b[i],K);for(i=0;i=0;getexp(n,b,a);
}int main(){freopen("polynomial.in","r",stdin);freopen("polynomial.out","w",stdout);int i,j;iv[0]=iv[1]=1;for(i=2;ifor(i=0;ifor(i=0;i=0;getinv(n,b,a); for(i=0;i=0;getintegration(n,a,b);for(i=0;i=0;getexp(n,b,a);  for(i=0;i=0;getinv(n,a,b);b[0]=ad(b[0],1);for(i=0;i=0;getln(n,b,a);a[0]=ad(a[0],1);for(i=0;i=0;getpow(n,a,b,K);for(i=0;i=0;getderivative(n,a,b);for(i=0;i' ');
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！