求助, WA 第二个点
查看原帖
求助, WA 第二个点
230249
xiaolilsq楼主2020/10/9 19:48

尝试对拍无果,只好来找万能的谷民求助。

思路就是先 ln\lnexp\exp

代码如下:

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ch() getchar()
#define pc(x) putchar(x)
using namespace std;
template<typename T>void read(T&x){
	char c;int f;
	for(c=ch(),f=1;c<'0'||c>'9';c=ch())if(c=='-')f=-f;
	for(x=0;c>='0'&&c<='9';c=ch())x=x*10+(c&15);x*=f;
}
template<typename T>void write(T x){
	static char q[64];int cnt=0;
	if(x==0)return pc('0'),void();
	if(x<0)pc('-'),x=-x;
	while(x)q[cnt++]=x%10,x/=10;
	while(cnt--)pc(q[cnt]+'0');
}
const int maxn=800005,mod=998244353,g_=3;
int mo(const int x){
	return x>=mod?x-mod:x;
}
int power(int a,int x){
	int re=1;
	while(x){
		if(x&1)re=1ll*re*a%mod;
		a=1ll*a*a%mod,x>>=1;
	}
	return re;
}
int rev[maxn];
void initNTT(int m,int&n){
	n=1;int cn=-1;
	while(n<m)n<<=1,++cn;
	for(int i=1;i<n;++i)
		rev[i]=(rev[i>>1]>>1)|((i&1)<<cn);
}
void NTT(int*F,int n,int rv){
	for(int i=0;i<n;++i)if(rev[i]<i)
		F[i]^=F[rev[i]]^=F[i]^=F[rev[i]];
	for(int mid=1;mid<n;mid<<=1){
		const int len=mid<<1,gn=power(g_,(mod-1)/len);
		for(int i=0;i<n;i+=len){
			for(int j=0,g=1;j<mid;++j,g=1ll*g*gn%mod){
				int l=i+j,r=l+mid;
				int L=F[l],R=1ll*F[r]*g%mod;
				F[l]=mo(L+R),F[r]=mo(mod-R+L);
			}
		}
	}
	if(!rv)return;reverse(F+1,F+n);int I=power(n,mod-2);
	for(int i=0;i<n;++i)F[i]=1ll*F[i]*I%mod;
}
int Inv[maxn];
void inv(int*F,int*G,int n){
	//G(x)=inv(F(x)) mod x^n;
	if(n==1)return G[0]=power(F[0],mod-2),void();
	inv(F,G,(n+1)>>1);for(int i=(n+1)>>1;i<n;++i)G[i]=0;
	int cp=n;initNTT((n+1)*2,n);
	for(int i=0;i<cp;++i)Inv[i]=F[i];for(int i=cp;i<n;++i)Inv[i]=G[i]=0;
	NTT(Inv,n,0);NTT(G,n,0);for(int i=0;i<n;++i)
		G[i]=1ll*G[i]*mo(mod-1ll*G[i]*Inv[i]%mod+2)%mod;
	NTT(G,n,1);for(int i=cp;i<n;++i)G[i]=0;
}
int Ln[maxn];
void ln(int*F,int*G,int n){
	//G(x)=ln(F(x)) mod x^n;
	for(int i=0;i<n;++i)Ln[i]=0;
	inv(F,Ln,n);int cp=n;
	initNTT((n+1)*2,n);
	for(int i=0;i<cp;++i)G[i]=1ll*F[i+1]*(i+1)%mod;
	for(int i=cp;i<n;++i)G[i]=Ln[i]=0;NTT(G,n,0);NTT(Ln,n,0);
	for(int i=0;i<n;++i)G[i]=1ll*G[i]*Ln[i]%mod;NTT(G,n,1);
	for(int i=cp-1;i>=1;--i)G[i]=1ll*G[i-1]*power(i,mod-2)%mod;
	G[0]=0;for(int i=cp;i<n;++i)G[i]=0;
}
int Exp[maxn];
void exp(int*F,int*G,int n){
	//G(x)=exp(F(x)) mod x^n;
	if(n==1)return G[0]=1,void();exp(F,G,(n+1)>>1);
	for(int i=(n+1)>>1;i<n;++i)G[i]=0;
	for(int i=0;i<n;++i)Exp[i]=0;ln(G,Exp,n);
	for(int i=0;i<n;++i)Exp[i]=mo(mod-Exp[i]+F[i]+(i==0));
	int cp=n;initNTT((n+1)*2,n);
	for(int i=cp;i<n;++i)Exp[i]=G[i]=0;NTT(G,n,0);NTT(Exp,n,0);
	for(int i=0;i<n;++i)G[i]=1ll*G[i]*Exp[i]%mod;
	NTT(G,n,1);for(int i=cp;i<n;++i)G[i]=0;
}
int Power[maxn];
void power(int*F,int*G,int n,int m0,int m1,int m2){
	//G(x)=power(F(x),m) mod x^n;
	//m0=m%mod m1=m%(mod-1) m2=stand for m
	if(m0==0){for(int i=0;i<n;++i)G[i]=(i==0);return;}
	int no=0;while(no<n&&F[no]==0)++no;
	if(1ll*no*m2>=n){for(int i=0;i<n;++i)G[i]=0;return;}
	int V=F[no],I=power(V,mod-2);
	for(int i=0;i+no<n;++i)G[i]=1ll*F[i+no]*I%mod,Power[i]=0;
	for(int i=n-no;i<n;++i)G[i]=Power[i]=0;ln(G,Power,n);
	for(int i=0;i<n;++i)Power[i]=1ll*Power[i]*m0%mod;
	exp(Power,G,n);V=power(V,m1);no*=m2;
	for(int i=n-1;i>=no;--i)G[i]=1ll*G[i-no]*V%mod;
	for(int i=no-1;i>=0;--i)G[i]=0;
}
int A[maxn],B[maxn];
int main(){
	int n,m=0,m_=0,m__=0;read(n);
	char c=ch();
	for(;c<'0'||c>'9';c=ch());
	for(;c>='0'&&c<='9';c=ch()){
		m=mo(1ll*m*10%mod+(c&15)),
		m_=(1ll*m_*10%(mod-1)+(c&15))%(mod-1);
		if(m__<=n)m__=m__*10+(c&15);
	}
	for(int i=0;i<n;++i)read(A[i]);
	power(A,B,n,m,m_,m__);
	for(int i=0;i<n;++i)write(B[i]),pc(" \n"[i==n-1]);
	return 0;
}
/*
所以,永远不要问丧钟为谁而鸣,它为你而鸣。
*/

2020/10/9 19:48
加载中...