牛顿迭代迭代式求助
查看原帖
牛顿迭代迭代式求助
553501
可爱的小棉羊楼主2024/4/12 16:46
#include<bits/stdc++.h>
using namespace std;
const long long   mod=998244353,g=3,ing=332748118;
int n;
long long a[300005],Ln[300004],res[3400005],tmp1[300005],tmp2[300005],inv[2][300004];
long long di[300004],Exp[2][600005];
long long fpow(long long a,long long b){
	long long ans=1;
	while(b){
		if(b&1)ans=ans*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return ans;
}
void ntt(long long*a,int n,bool 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;
		if(f==1)wn=fpow(g,(mod-1)/(h<<1));
		else wn=fpow(ing,(mod-1)/(h<<1));
		for(int j=0;j<n;j+=(h<<1)){
			long long w=1;
			for(int k=0;k<h;k++,w=w*wn%mod){
				long long x=a[j+k],y=a[j+h+k]*w%mod;
				a[j+k]=(x+y)%mod;
				a[j+h+k]=(x-y+mod)%mod;
			}
		}
	}
	if(f==0){
		long long inv=fpow(n,mod-2);
		for(int i=0;i<n;i++)a[i]=a[i]*inv%mod;
	}
}
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>>1);i++)tmp1[i]=a[i];
	for(int i=0;i<(n>>1);i++)tmp2[i]=b[i];
	ntt(tmp1,n,1);
	ntt(tmp2,n,1);
	for(int i=0;i<n;i++)tmp1[i]=tmp1[i]*tmp2[i]%mod;
	ntt(tmp1,n,0);
	for(int i=0;i<n;i++)a[i]=tmp1[i];
}
void calrev(int n,int k){
	for(int i=0;i<n;i++)res[i]=(res[i>>1]>>1)|((i&1)<<(k-1));
}
bool polyinv(long long *a,int n){
	memset(inv[0],0,sizeof(inv[0]));
	n--;
	bool t=0;
	int bas=1,lim=2,k=1;
	calrev(lim,k);
	inv[0][0]=fpow(a[0],mod-2); 
	while(bas<=(n<<1)){
		memset(inv[t^1],0,sizeof(inv[t^1]));
		t^=1;
		for(int i=0;i<bas;i++)inv[t][i]=(inv[t^1][i]<<1)%mod;
		
		mul(inv[t^1],inv[t^1],lim);
		mul(inv[t^1],a,lim);
		for(int i=0;i<bas;i++)inv[t][i]=(inv[t][i]-inv[t^1][i]+mod)%mod;
		bas<<=1;
		lim<<=1;
		k++;
		if(bas<=(n<<1))calrev(lim,k);
	}
	return t;
}
void polyln(long long* a,int n){
	memset(Ln,0,sizeof(Ln));
	int t=polyinv(a,n);
	for(int i=1;i<n;i++)di[i-1]=a[i]*i%mod;
	for(int i=0;i<n;i++)a[i]=inv[t][i];
	int s=1,k=0;
	while(s<=(n<<1)){
		s<<=1;
		k++;
	}
	calrev(s,k);
	mul(di,a,s);
	for(int i=1;i<n;i++)Ln[i]=di[i-1]*fpow(i,mod-2)%mod;
}
//long long tmp3[600006];
int polyexp(long long* a,int n){
	Exp[0][0]=1;
	bool t=0;
	n--;
	int bas=1,lim=2,k=1;
	while(bas<=(n<<1)){
		memset(Exp[t^1],0,sizeof(Exp[t^1]));
		polyln(Exp[t],bas);
		for(int i=0;i<bas;i++)Exp[t^1][i]=(1-Ln[i]+a[i]+mod)%mod;
		calrev(lim,k);
		mul(Exp[t^1],Exp[t],lim);
		lim<<=1;
		bas<<=1;
		t^=1;
		k++;
	}
	return t;
}
int main(){
	//cout<<fpow(3,mod-2)<<endl;
	cin>>n;
	for(int i=0;i<n;i++)cin>>a[i];
	int t=polyexp(a,n);
	for(int i=0;i<n;i++)cout<<Exp[t][i]<<" ";
} 
2024/4/12 16:46
加载中...