MnZn求助
查看原帖
MnZn求助
553501
可爱的小棉羊楼主2024/3/22 14:22
#include<bits/stdc++.h>
using namespace std;
const int p=998244353,g=3;
long long fpow(long long a,long long b){
	b=(b+(p-1))%(p-1);
	long long ans=1;
	while(b){
		if(b&1)ans=ans*a%p;
		a=a*a%p;
		b>>=1;
	}
	return ans;
}
long long a[400006],n;
long long der[400005],res[400005];
long long b[2][400005],bas=1,k=1,lim=2;
int tmp1[400006],tmp2[400005];
bool t;
void ntt(long long* a,int n,int f){
	for(int i=0;i<n;i++)if(i<res[i])swap(a[i],a[res[i]]);
	
	for(int h=1;h<n;h<<=1){
		long long wn=fpow(g,(p-1)/(h<<1)*f);
		for(int j=0;j<n;j+=(h<<1)){
			long long w=1;
			for(int k=0;k<h;k++,w=w*wn%p){
				long long x=a[j+k],y=w*a[j+k+h]%p;
				a[j+k]=(x+y)%p;
				a[j+k+h]=(x-y+p)%p;
			}
		}
	}
	if(f==-1){
		int inv=fpow(n,-1);
		for(int i=0;i<n;i++)a[i]=a[i]*inv%p;
	}
}
void mul(long long* a,long long* b,int n){
	memset(tmp1,0,sizeof(tmp1));
	memset(tmp2,0,sizeof(tmp2));
	for(int i=0;i<n;i++)tmp1[i]=a[i];
	for(int i=0;i<n;i++)tmp2[i]=b[i];
	ntt(a,n,1);
	ntt(b,n,1);
	for(int i=0;i<n;i++)a[i]=a[i]*b[i]%p;
	ntt(a,n,-1);
}
int main(){
	cin>>n;
	for(int i=0;i<n;i++)cin>>a[i];
	for(int i=1;i<n;i++)der[i-1]=i*a[i]%p;
	b[0][0]=fpow(a[0],-1);
	n--;
	while(bas<=(n<<1)){
		memset(b[t^1],0,sizeof(b[t^1]));
		for(int i=0;i<bas;i++)b[t^1][i]=(b[t][i]<<1)%p;
		for(int i=1;i<lim;i++)res[i]=(res[i>>1]>>1)|((i&1)<<(k-1));
		mul(b[t],b[t],lim);
		mul(b[t],a,lim);
		for(int i=0;i<bas;i++)b[t^1][i]=(b[t^1][i]-b[t][i]+p)%p;
		bas<<=1;
		t^=1;
		
		lim<<=1;
		k++;
		
	}
	t^=1;
	lim>>=1;
	mul(der,b[t],lim);
	a[0]=0;
	for(int i=0;i<n;i++)a[i+1]=fpow(i+1,-1)*der[i]%p;
	for(int i=0;i<=n;i++)cout<<b[t][i]<<" ";
} 
2024/3/22 14:22
加载中...