35pts 求卡常
查看原帖
35pts 求卡常
60864
tiger2005楼主2020/7/31 17:55

RT

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<stack>
using namespace std;
int ksm(int x,int y,int m){
	x%=m;
	long long ret=1,bas=x;
	while(y){
		if(y&1)	ret=(ret*bas)%m;
		y>>=1;bas=(bas*bas)%m;
	}
	return (int)ret;
}
namespace PolyIntNamespace{
	const int MAXL=2000010;
	int rev[MAXL];
	void makeRev(int l){
		for(int i=0,j=(1<<l);i<j;i++)
			rev[i]=((rev[i>>1]>>1)|((i&1)<<(l-1)));
	}
	typedef pair<int,long long * > PolyInt;
	#define newPoly(i) make_pair((i),new long long[MAXL])
	#define copyInfo(A,B) for(int e=0;e<A.first;e++)A.second[e]=B.second[e]
	const int MD = 998244353 , _G = 3;
	void input(PolyInt & c,int a){
	    long long b;
		for(int i=0;i<a;i++){
			scanf("%lld",&b);
			c.second[i]=b;
		}
	}
	void NTT(PolyInt & Q,int p){
		int h=_G;
		if(p==-1)	h=ksm(_G,MD-2,MD);
		for(int i=0;i<Q.first;i++)
			if(i<rev[i]){
	            long long t=Q.second[i];
	            Q.second[i]=Q.second[rev[i]];
	            Q.second[rev[i]]=t;
	        }
		for(int mid=1;mid<Q.first;mid<<=1){
			long long W=ksm(h,(MD-1)/(mid<<1),MD);
			int R=mid<<1;
			for(int i=0;i<Q.first;i+=R){
				long long w=1;
				for(int j=0;j<mid;j++,w=(w*W)%MD){
					long long x=Q.second[i+j],y=(w*Q.second[i+j+mid])%MD;
					Q.second[j+i]=(x+y)%MD;
					Q.second[j+i+mid]=(x-y+MD)%MD;
				}
			}
		}
		if(p==-1){
			long long leninv=ksm(Q.first,MD-2,MD);
			for(int i=0;i<Q.first;i++)
				Q.second[i]=(Q.second[i]*leninv)%MD;
		}
	}
	inline PolyInt mul(PolyInt Q,PolyInt a){
		int N=Q.first,M=a.first;
		int L=1;int l=0;
		while(L<N+M)	L<<=1,l++;
		PolyInt ret=newPoly(L);a.first=L;
		for(int i=0;i<N;i++)
			ret.second[i]=Q.second[i];
		for(int i=M;i<L;i++)
			a.second[i]=0;
		makeRev(l);
		NTT(ret,1);NTT(a,1);
		for(int i=0;i<L;i++)	ret.second[i]=(ret.second[i]*a.second[i])%MD;
		NTT(ret,-1);
		return ret;
	}
	void release(PolyInt & Q,int o){
		if(Q.first>o)	Q.first=o;
		while(Q.first<o)	Q.second[Q.first++]=0;
	}
	void printInt(PolyInt Q,int ll){
		for(int i=0;i<ll;i++)
			printf("%lld ",Q.second[i]);
	}
	inline PolyInt getInv(PolyInt & Q){
		int L=1,l=0;
		while(L<Q.first)	L<<=1,l++;
		PolyInt A=newPoly(Q.first);
	    copyInfo(A,Q);
		release(A,L);
		PolyInt B=newPoly(1);
		B.second[0]=ksm(A.second[0],MD-2,MD);
		for(int i=2,k=2;i<=L;i<<=1,++k){
			release(B,i<<1);
	        PolyInt x=newPoly(i);
	        copyInfo(x,A);
	        release(x,i<<1);
			makeRev(k);
			NTT(B,1);NTT(x,1);
			for(int j=0;j<(i<<1);j++)
				B.second[j]=(2ll-(x.second[j]*B.second[j])%MD+MD)%MD*B.second[j]%MD;
	    	NTT(B,-1);release(B,i);
		}
		release(B,Q.first);
		return B;
	}
//	inline PolyInt getDeri(PolyInt & Q){
//		PolyInt ret=newPoly(Q.first);
//		for(int i=0;i<Q.first-1;i++)
//			ret.second[i]=(1ll*Q.second[i+1]*(i+1))%MD;
//		return ret;
//	}
//	inline PolyInt getInte(PolyInt & Q){
//		PolyInt ret=newPoly(Q.first+1);
//		for(int i=1;i<=Q.first;i++)
//			ret.second[i]=(1ll*Q.second[i-1]*ksm(i,MD-2,MD))%MD;
//		return ret;
//	}
//	inline PolyInt toLen(PolyInt & Q,int o){
//		PolyInt ret=Q;
//		release(ret,o);
//		return ret;
//	}
	inline PolyInt getLn(PolyInt & Q){
		PolyInt q=newPoly(Q.first);
		for(int i=0;i<Q.first-1;i++)
			q.second[i]=(1ll*Q.second[i+1]*(i+1))%MD;
		q.second[Q.first-1]=0;
		q=mul(q,getInv(Q));
		release(q,Q.first);
		for(int i=q.first-1;i>0;i--)
			q.second[i]=(1ll*q.second[i-1]*ksm(i,MD-2,MD))%MD;
		q.second[0]=0;
		return q;
	}
	inline PolyInt getExp(PolyInt & Q){
		int L=1,l=0;
		while(L<Q.first)	L<<=1,l++;
		PolyInt B=newPoly(1);
		B.second[0]=1;
		for(int i=2,k=2;i<=L;i<<=1,++k){
			release(B,i<<1);
			PolyInt Bb=B;
			Bb=getLn(Bb);
			for(int j=0;j<i;j++)
				Bb.second[j]=((j==0)-Bb.second[j]+Q.second[j]+MD)%MD;
			B=mul(B,Bb);release(B,i);
		}
		release(B,Q.first);
		return B;
	}
	inline PolyInt getPow(PolyInt & Q,int p){
		PolyInt q=getLn(Q);
		for(int i=0;i<q.first;i++)
			q.second[i]=(q.second[i]*p)%MD;
		return getExp(q); 
	}
};
using namespace PolyIntNamespace;
int N;
char BAS[100010];
int main(){
	scanf("%d %s",&N,BAS);
	PolyInt A=newPoly(N);
	input(A,N);
	int p=0;
	for(int i=0;BAS[i];i++)
		p=(1ll*p*10+BAS[i]-'0')%MD;
	printInt(getPow(A,p),N);
	return 0;
}
2020/7/31 17:55
加载中...