题解 P5273 【【模板】多项式幂函数 (加强版)】
周道_Althen
·
·
题解
广告:【多项式的操作大赏】
$\ \ \ \ \ \ \ $了解到呢，很多同学是化成下面的式子来处理的：
$$A^k=\left({\frac{A}{A_0}}\right)^k\times A_0^k$$
$\ \ \ \ \ \ \ $这样子就可以成功把 $a[0]$ 化成对于 $1$ ，然后单独 $a[0]=0$ 处理，剩下的就是套$ln$，$exp$板子了。
# $\ \ \ \ \ \ \ $但是这样有没有必要呢？显然是没有必要的：
$\ \ \ \ \ \ \ $首先考虑为什么一定要保证$a[0]=1$？
$\ \ \ \ \ \ \ $因为这样可以保证 $ln(A)_0\times k=0$ ，从而方便算出$exp$。
$\ \ \ \ \ \ \ $那么为什么？当 $ln(A)_0\times k=0$ 等于其他数的时候，不方便算$exp$了呢？
$\ \ \ \ \ \ \ $我们得回忆一下$exp$是怎么求的:
$\ \ \ \ \ \ \ $令我们要求的是 $A$ 的指数函数 $B$，既是：
$$B=e^A$$
$\ \ \ \ \ \ \ $变形得：
$$\ln(B)-A=0$$
$\ \ \ \ \ \ \ $设$F(B)=\ln (B)-A$，我们要求的就是 $F$的零点，这里是吧多项式当做常量了，牛顿迭代得到的式子（注意这里B后面的括号的迭代版本的意思，不是多项式的项，下标才是表示的项）：
$$B(x)=B(x-1)-\frac{F\left(B(x-1)\right)}{F'\left(B(x-1)\right)}$$
$\ \ \ \ \ \ \ $由$F'(B)=\frac{1}{B}$，化简牛顿迭代的公式：
$$\begin{aligned}B(x)&=B(x-1)-B(x-1)*F\left(B(x-1)\right)\\&=B(x-1)-B(x-1)*\ln \left(B(x-1)\right)-A\\&=B(x-1)* \left(1-\ln \left(B(x-1)\right)-A \right)\end{aligned}$$
$\ \ \ \ \ \ \ $在倍增求解的过程中，我们只需要知道第一个版本是多少，也就是 $B_0$ ，常数项的值就知道了：
$\ \ \ \ \ \ \ $在一般情况下，这个问题很显然，因为：$e^0=1$，所以说当$A_0=0$的时候，他的指数函数 $B$，$B_0=1$，第一个版本就确定了。
$\ \ \ \ \ \ \ $当$A_0\neq0$的时候，第一个版本确实不好求。
# $\ \ \ \ \ \ \ $回到题目：
$\ \ \ \ \ \ \ $好在我们很清楚的是：
$\ \ \ \ \ \ \ $对于求$B=A^k$，有：
$$B=exp(ln(A)\times k)$$
$\ \ \ \ \ \ \ $好了，我们要求的第一个版本就是$exp(ln(A)\times k)$的常数项，也就是$B$的常数项，那么常数项是多少呢？
# $\ \ \ \ \ \ \ $当然是$A_0^k$啊。
$\ \ \ \ \ \ \ $到此，感觉有理有据的，可是实际操作写下来，怎么只有$90$分呢？
$\ \ \ \ \ \ \ $当$a[0]=0$时，第一个版本应该是$B_0=0$，可是……版本真的可以为$0$吗？
$\ \ \ \ \ \ \ $我们是要求 $F'(B)=\frac{1}{B}$ 的，分母当然不能为 $0$ 了，所以说我们还是要单独处理 $a[0]=0$ 的情况的。
$\ \ \ \ \ \ \ $把为$0$的前缀提出来，然后算，最后在答案前面加上提出的长度乘上$k$个$0$即可，具体可以看丑陋的代码：
$\ \ \ \ \ \ \ $因为是直接贴的辣鸡板子，所以说跑得很慢：
```cpp
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<string>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<cmath>
#include<cctype>
using namespace std;
const int inf=0x7fffffff;
const double eps=1e-10;
const double pi=acos(-1.0);
//char buf[1<<15],*S=buf,*T=buf;
//char getch(){return S==T&&(T=(S=buf)+fread(buf,1,1<<15,stdin),S==T)?0:*S++;}
inline int read(){
int x=0,f=1;char ch;ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-') f=0;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch&15);ch=getchar();}
if(f)return x;else return -x;
}
const int N=3e6+10;
const int mod=998244353,mod_g=3;
int K;
int R[N];
int power(int a,int b){
int ans=1;
for(;b;b>>=1,a=1ll*a*a%mod)if(b&1)ans=1ll*ans*a%mod;
return ans;
}
#define Inv(x) power(x,mod-2)
int Polynomial_init(int n){
int len;for(len=1;len<n;len<<=1);
return len;
}
void NTT(int *a,int f,int la){
int n=la;
for(int i=0;i<n;i++)if(i<R[i])swap(a[i],a[R[i]]);
for(int i=1;i<n;i<<=1){
int gn=power(mod_g,(mod-1)/(i<<1));
for(int j=0;j<n;j+=(i<<1)){
int g=1;
for(int k=0;k<i;k++,g=1ll*g*gn%mod){
int x=a[j+k],y=1ll*g*a[i+j+k]%mod;
a[j+k]=(x+y)%mod;a[i+j+k]=(x-y+mod)%mod;
}
}
}
if(f==-1){
reverse(a+1,a+n);
int inv=Inv(n);
for(int i=0;i<n;i++)a[i]=1ll*a[i]*inv%mod;
}
}
int Convolution(int *a,int *b,int la,int lb){
int n=la,m=lb;
int L=0;for(m+=n,n=1;n<=m;n<<=1)L++;
for(int i=0;i<n;i++)R[i]=(R[i>>1]>>1)|((i&1)<<(L-1));
NTT(a,1,n);NTT(b,1,n);
for(int i=0;i<=n;i++)a[i]=1ll*a[i]*b[i]%mod;
NTT(a,-1,n);
return m;
}
int I[N],J[N];
int Multiplication(int *a,int *b,int *c,int la,int lb){
int n=la,m=lb;
int L=0;for(m+=n,n=1;n<=m;n<<=1)L++;
for(int i=0;i<n;i++)R[i]=(R[i>>1]>>1)|((i&1)<<(L-1));
for(int i=0;i<=la;++i) I[i]=a[i];
for(int i=0;i<=lb;++i) J[i]=b[i];
NTT(I,1,n);NTT(J,1,n);
for(int i=0;i<=n;i++)c[i]=1ll*I[i]*J[i]%mod,I[i]=J[i]=0;
NTT(c,-1,n);
}
int C[N];
void Inverse(int *a,int *b,int len){
if(len==1){b[0]=Inv(a[0]);return;}
Inverse(a,b,(len+1)>>1);
int L=0,n=1;
for(;n<(len<<1);n<<=1)L++;
for(int i=1;i<n;i++)R[i]=(R[i>>1]>>1)|((i&1)<<(L-1));
for(int i=0;i<len;i++)C[i]=a[i];
for(int i=len;i<n;i++)C[i]=0;
NTT(C,1,n);NTT(b,1,n);
for(int i=0;i<=n;i++)b[i]=1ll*(2ll-1ll*C[i]*b[i]%mod+mod)%mod*b[i]%mod;
NTT(b,-1,n);
for(int i=len;i<n;i++)b[i]=0;
}
int H[N];
void Division(int *a,int *b,int la,int lb,int *Quotient,int *Remainder){
int n=la,m=lb;
reverse(a,a+1+n),reverse(b,b+1+m);
int len=1;while(len<=n-m)len<<=1;
memset(C,0,sizeof(C));
Inverse(b,H,len);
Multiplication(a,H,Quotient,n-m,n-m);
reverse(Quotient,Quotient+n-m+1);
reverse(a,a+n+1),reverse(b,b+m+1);
Multiplication(Quotient,b,Remainder,n-m,m);
for(int i=0;i<m;++i)Remainder[i]=(a[i]-Remainder[i]+mod)%mod;
}
void Derivation(int *a,int *b,int n){
for(int i=1;i<n;i++)
b[i-1]=1ll*i*a[i]%mod;
b[n-1]=0;
}
void Integral(int *a,int *b,int n){
for(int i=1;i<n;i++)
b[i]=1ll*Inv(i)*a[i-1]%mod;
b[0]=0;
}
int ln_a[N],ln_b[N];
void Logarithmic(int *a,int *b,int n){
memset(ln_a,0,sizeof(ln_a));
memset(ln_b,0,sizeof(ln_b));
Derivation(a,ln_a,n);
memset(C,0,sizeof(C));
Inverse(a,ln_b,n);
Convolution(ln_a,ln_b,n,n);
Integral(ln_a,b,n);
}
int D[N];
void Exponential(int *a,int *b,int len){
if(len==1){return;}
Exponential(a,b,len>>1),Logarithmic(b,D,len);
D[0]=(1ll*a[0]+1ll-D[0]+mod)%mod;
for(int i=1;i<len;++i) D[i]=(1ll*a[i]-D[i]+mod)%mod;
Convolution(b,D,len<<1,len<<1);
for(int i=len;i<(len<<1);++i) b[i]=D[i]=0;
}
int p_a[N];
void Power(int *a,int *b,int len){
Logarithmic(a,p_a,len);
for(int i=1;i<=len;i++)p_a[i]=1ll*p_a[i]*K%mod;
b[0]=power(a[0],K%(mod-1));
Exponential(p_a,b,len);
}
int n,F[N],G[N],low;
int main()
{
n=read();K=read();
for(int i=0;i<n;i++)F[i]=read();
for(int i=0;i<=n;++i){if(!F[i])continue;low=i;break;}
if(low)for(int i=low;i<n;++i)F[i-low]=F[i],F[i]=0;
Power(F,G,Polynomial_init(n));
if(low){
if(1ll*low*K>n)low=n;
else low*=K;
for(int i=n-1;i>=0;--i){
if(i+low<n)G[i+low]=G[i];
G[i]=0;
}
}
for(int i=0;i<n;i++)printf("%d ",G[i]);
return 0;
}
```