【Cogs2187】帕秋莉的超级多项式（多项式运算）

时间：2023-01-08 20:45:27

【Cogs2187】帕秋莉的超级多项式（多项式运算）

题面

Cogs

题解

多项式运算模板题

只提供代码了。。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<set>

#include<map>

#include<vector>

#include<queue>

using namespace std;

#define ll long long

#define RG register

#define MAX 444444

const int MOD=998244353;

const int Phi=MOD-1;

const int gr=3;

inline int read()

{

    RG int x=0,t=1;RG char ch=getchar();

    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

    if(ch=='-')t=-1,ch=getchar();

    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

    return x*t;

}

int fpow(int a,int b)

{

	int s=1;

	while(b){if(b&1)s=1ll*s*a%MOD;a=1ll*a*a%MOD;b>>=1;}

	return s;

}

int r[MAX],N,l,M;

int Og[MAX];

void NTT(int *P,int opt,int n)

{

	for(N=1,l=0;N<n;N<<=1)++l;

	for(RG int i=0;i<N;++i)r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));

	for(RG int i=0;i<N;++i)if(i<r[i])swap(P[i],P[r[i]]);

	for(RG int i=1;i<N;i<<=1)

	{

		RG int W=fpow(gr,Phi/(i<<1));Og[0]=1;

		for(RG int j=1;j<i;++j)Og[j]=1ll*Og[j-1]*W%MOD;

		for(RG int p=i<<1,j=0;j<N;j+=p)

			for(RG int k=0;k<i;++k)

			{

				RG int X=P[j+k],Y=1ll*Og[k]*P[i+j+k]%MOD;

				P[j+k]=(X+Y)%MOD;P[i+j+k]=(X+MOD-Y)%MOD;

			}

	}

	if(opt==-1)

	{

		reverse(&P[1],&P[N]);

		for(RG int i=0,inv=fpow(N,MOD-2);i<N;++i)P[i]=1ll*P[i]*inv%MOD;

	}

}

int inv[MAX];

void initinv(int N)

{

	inv[0]=inv[1]=1;

	for(RG int i=2;i<N;++i)inv[i]=1ll*inv[MOD%i]*(MOD-MOD/i)%MOD;

}

int A[MAX],B[MAX];

void Inv(int *a,int *b,int len)

{

	if(len==1){b[0]=fpow(a[0],MOD-2);return;}

	Inv(a,b,len>>1);

	for(RG int i=0;i<len;++i)A[i]=a[i],B[i]=b[i];

	NTT(A,1,len<<1);NTT(B,1,len<<1);

	for(RG int i=0;i<(len<<1);++i)A[i]=1ll*A[i]*B[i]%MOD*B[i]%MOD;

	NTT(A,-1,len<<1);

	for(RG int i=0;i<len;++i)b[i]=(b[i]+b[i])%MOD;

	for(RG int i=0;i<len;++i)b[i]=(b[i]+MOD-A[i])%MOD;

	for(RG int i=0;i<(len<<1);++i)A[i]=B[i]=0;

}

int C[MAX],D[MAX],inv2=fpow(2,MOD-2);

void Sqrt(int *a,int *b,int len)

{

	if(len==1){b[0]=sqrt(a[0]);return;}

	Sqrt(a,b,len>>1);

	for(RG int i=0;i<=len;++i)C[i]=a[i];

	Inv(b,D,len);

	NTT(C,1,len<<1);NTT(D,1,len<<1);

	for(RG int i=0;i<(len<<1);++i)D[i]=1ll*C[i]*D[i]%MOD;

	NTT(D,-1,len<<1);

	for(RG int i=0;i<len;++i)b[i]=1ll*(b[i]+D[i])%MOD*inv[2]%MOD;

	for(RG int i=0;i<=(len<<1);++i)C[i]=D[i]=0;

}

void Dao(int *a,int *b,int len)

{

	for(RG int i=1;i<len;++i)b[i-1]=1ll*i*a[i]%MOD;

	b[len]=b[len-1]=0;

}

void Jifen(int *a,int *b,int len)

{

	for(RG int i=1;i<len;++i)b[i]=1ll*a[i-1]*inv[i]%MOD;

	b[0]=0;

}

void Getln(int *a,int *b,int len)

{

	int A[MAX],B[MAX];

	memset(A,0,sizeof(A));memset(B,0,sizeof(B));

	Dao(a,A,len);

	Inv(a,B,len);

	NTT(A,1,len<<1);NTT(B,1,len<<1);

	for(RG int i=0;i<(len<<1);++i)A[i]=1ll*A[i]*B[i]%MOD;

	NTT(A,-1,len<<1);

	Jifen(A,b,len);

	for(RG int i=0;i<(len<<1);++i)A[i]=B[i]=0;

}

int E[MAX];

void Exp(int *a,int *b,int len)

{

	if(len==1){b[0]=1;return;}

	Exp(a,b,len>>1);

	for(RG int i=0;i<len;++i)D[i]=b[i];

	Getln(b,E,len);

	for(RG int i=0;i<len;++i)E[i]=(MOD-E[i]+a[i])%MOD;E[0]=(E[0]+1)%MOD;

	NTT(E,1,len<<1);NTT(D,1,len<<1);

	for(RG int i=0;i<(len<<1);++i)D[i]=1ll*D[i]*E[i]%MOD;

	NTT(D,-1,len<<1);

	for(RG int i=0;i<len;++i)b[i]=D[i];

	for(RG int i=0;i<(len<<1);++i)D[i]=E[i]=0;

}

void FastPow(int *a,int *b,int K,int len)

{

	int E[MAX];memset(E,0,sizeof(E));

	Getln(a,E,len);

	for(RG int i=0;i<len;++i)E[i]=1ll*K*E[i]%MOD;

	Exp(E,b,len);

}

int X[MAX],Y[MAX];

int n,K;

int main()

{

	freopen("polynomial.in","r",stdin);

	freopen("polynomial.out","w",stdout);

	n=read();K=read();

	for(RG int i=0;i<n;++i)X[i]=read();

	int N;for(N=1;N<=n;N<<=1);initinv(N);

	Sqrt(X,Y,N);memset(X,0,sizeof(X));//for(int i=0;i<n;++i)printf("%d ",Y[i]);puts("");

	Inv(Y,X,N);memset(Y,0,sizeof(Y));//for(int i=0;i<n;++i)printf("%d ",X[i]);puts("");

	Jifen(X,Y,N);memset(X,0,sizeof(X));//for(int i=0;i<n;++i)printf("%d ",Y[i]);puts("");

	Exp(Y,X,N);memset(Y,0,sizeof(Y));//for(int i=0;i<n;++i)printf("%d ",X[i]);puts("");

	Inv(X,Y,N);memset(X,0,sizeof(X));Y[0]=(Y[0]+1)%MOD;//for(int i=0;i<n;++i)printf("%d ",Y[i]);puts("");

	Getln(Y,X,N);memset(Y,0,sizeof(Y));X[0]=(X[0]+1)%MOD;//for(int i=0;i<n;++i)printf("%d ",X[i]);puts("");

	FastPow(X,Y,K,N);memset(X,0,sizeof(X));

	Dao(Y,X,n);for(RG int i=0;i<n;++i)printf("%d ",X[i]);puts("");

	return 0;

}

相关文章