COGS 2189. [HZOI 2015] 帕秋莉的超级多项式（牛顿迭代）

传送门

题意：
求:

题解：

依次进行牛顿迭代即可。

注意多项式$k$次方不需要快速幂：
$$\ln G(x)=\ln (F(x)^k) =k \ln F(x)$$
多项式再$exp$即可。

#include 
typedef long long LL;
using namespace std;
inline int rd() {char ch=getchar(); int i=0,f=1;while(!isdigit(ch)) {if(ch=='-')f=-1; ch=getchar();}while(isdigit(ch)) {i=(i<<1)+(i<<3)+ch-'0'; ch=getchar();}return i*f;
}
inline void W(int x){static int buf[50];if(!x) {putchar('0'); return;}if(x<0) {putchar('-');x=-x;}while(x) {buf[++buf[0]]=x%10; x/=10;}while(buf[0]) {putchar(buf[buf[0]--]+'0');}
}
const int N=1e5+50;
const int mod=998244353;
const int G=3;
const int inv2=499122177;
inline int power(int a,int b) {int rs=1;for(;b;b>>=1,a=(LL)a*a%mod) if(b&1) rs=(LL)rs*a%mod;return rs;
}
int n,p,inv[N*8];
int k,f[N*8],g[N*8],ig[N*8],ep[N*8],lp[N*8],ip[N*8],rp[N*8],rp2[N*8],w[N*8],pos[N*8];
inline void init() {for(int i=1;i1)?((pos[i>>1]>>1)^(k>>1)):(pos[i>>1]>>1);
}
inline void dft(int *a,int o=1) {for(int i=1;ii)&&(swap(a[pos[i]],a[i]),0);for(int bl=1;bl1){int tl=bl<<1,wn=power(G,(mod-1)/tl); w[0]=1;for(int i=1;i1]*wn%mod;for(int bg=0;bgfor(int j=0;jint &t1=a[bg+j],&t2=a[bg+j+bl],t3=(LL)t2*w[j]%mod;t2=(t1-t3<0?t1-t3+mod:t1-t3);t1=(t1+t3>=mod?t1+t3-mod:t1+t3);}}if(o!=1) {const int inv=power(k,mod-2);for(int i=0;iinline void calc_inverse(int *a,int *b,int len) {if(len==1) {b[0]=power(a[0],mod-2); return;}if(len!=1) calc_inverse(a,b,len>>1); k=len<<1; init();for(int i=0;ifor(int i=len;i0;for(int i=(len>>1);i0;dft(b); dft(ip);for(int i=0;i2ll*b[i]-(LL)b[i]*b[i]%mod*ip[i]%mod)%mod;dft(b,-1); reverse(b+1,b+k);for(int i=len;i0;
}
inline void calc_ln(int *a,int *b,int len) {calc_inverse(a,lp,len); k=len<<1; init();for(int i=0;i1;i++) b[i]=(LL)a[i+1]*(i+1)%mod;for(int i=len-1;i0;dft(lp); dft(b);for(int i=0;i1); reverse(b+1,b+k);for(int i=len-1;i>=1;i--) b[i]=(LL)b[i-1]*inv[i]%mod;for(int i=len;i0;b[0]=0; return;
}
inline void calc_exp(int *a,int *b,int len) {if(len==1) {b[0]=1; return;}if(len!=1) calc_exp(a,b,len>>1);calc_ln(b,ep,len);k=len<<1; init();for(int i=0;i0]++;for(int i=len;i0);dft(ep); dft(b);for(int i=0;i1); reverse(b+1,b+k);for(int i=len;i0;
}
inline void calc_root(int *a,int *b,int len) {if(len==1) {b[0]=sqrt(a[0]); return;}if(len!=1) calc_root(a,b,len>>1);calc_inverse(b,rp,len);k=len<<1; init();for(int i=0;ifor(int i=len;i0;dft(rp); dft(rp2);for(int i=0;i1); reverse(rp+1,rp+k);for(int i=0;ifor(int i=len;i0;
}
int main() {n=rd(), p=rd(); inv[1]=1;for(int i=2;ifor(int i=0;iint len=1; for(;len1);calc_root(f,g,len);calc_inverse(g,ig,len);for(int i=1;i1]*inv[i]%mod;f[0]=0;calc_exp(f,g,len);calc_inverse(g,ig,len);for(int i=0;i0]++; calc_ln(f,g,len);g[0]++; calc_ln(g,ig,len);for(int i=0;ifor(int i=0;i1;i++) f[i]=(LL)f[i+1]*(i+1)%mod;for(int i=0;i1;i++) W(f[i]),putchar(' ');W(0); putchar('\n');
}

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