样例过不去求条
查看原帖
样例过不去求条
728778
hdkk楼主2024/7/23 19:39

蒟蒻照着题解写的过不了,要崩溃了,求救

#include<bits/stdc++.h>
using namespace std;
const int md=998244353,g=3;
int rev[1000005];
int inline inc1(int x,int y)
{
	return x-y+(x-y<0?md:0);
}
int inline inc(int x,int y)
{
	return x+y-(x+y>=md?md:0);
}
int ks(int a,int b)
{
	int res=1;
	while(b)
	{
		if(b&1) res=1ll*res*a%md;
		a=1ll*a*a%md;
		b>>=1; 
	}
	return res;
}
void ntt(int *f,int n,int inv)
{
	for(int i=0;i<n;i++)
		if(i>rev[i]) swap(f[i],f[rev[i]]);
	for(int len=1;len<n;len<<=1)
	{
		int tmp=ks(g,(md-1)/(len*2));
		if(inv) tmp=ks(tmp,md-2);
		for(int l=0;l<n;l+=len*2)
		{
			int w=1;
			for(int k=0;k<len;k++)	
			{
				int x=f[l+k],y=1ll*w*f[l+k+len]%md;
				f[l+k]=(x+y)%md;
				f[l+k+len]=(x-y+md)%md;
				w=1ll*w*tmp%md;
			}
		}
	}
}
int c[1000005],F[1000005],G[1000005];
void pinv(int n,int *a,int *b)
{
	if(n==1){
		b[0]=ks(a[0],md-2);
		return;
	}
	pinv((n+1)/2,a,b);
	int m=1,len=0;
	for(;m<(n<<1);m<<=1,len++);
	for(int i=1;i<m;i++) rev[i]=((rev[i>>1]>>1)|((i&1)<<(len-1)));
	for(int i=0;i<n;i++) c[i]=a[i];
	for(int i=n;i<m;i++) c[i]=0;
	ntt(c,m,0),ntt(b,m,0);
	for(int i=0;i<m;i++) b[i]=1ll*(2-1ll*c[i]*b[i]%md+md)%md*b[i]%md;
	ntt(b,m,1);
	for(int i=n;i<m;i++) b[i]=0;
}
int main()
{
	int n;
	cin>>n;
	for(int i=0;i<n;i++) cin>>F[i],F[i]%=md;
	pinv(n,F,G);
	for(int i=0;i<n;i++) cout<<G[i]<<' ';
}
2024/7/23 19:39
加载中...