Mn Zn 求助
查看原帖
Mn Zn 求助
223560
_HL_楼主2022/2/1 13:19

为啥样例能过 评测保龄了 qnq

#include <bits/stdc++.h>
#define mod 998244353
#define G 3
#define Gi 332748118
#define int long long
const int N=1e7+3;
using namespace std;
int f[N],g[N];
int len;
inline int read()
{
	int x=0;
	char c=getchar();
	while(c<'0'||c>'9')c=getchar();
	while(c>='0'&&c<='9')
	{
		x=(x<<1)+(x<<3)+c-'0';
		c=getchar();
	}
	return x;
}
inline int mul(int a,int b)
{
	return (a*b)%mod;
}
inline int add(int a,int b)
{
	return (a+b)%mod;
}
inline int sub(int a,int b)
{
	return (a-b+mod)%mod;
}
inline int qpow(int a,int b)
{
	int res=1;
	while(b)
	{
		if(b%2==1)res=mul(res,a);
		b>>=1;
		a=mul(a,a);
	}
	return res;
}
inline void ntt(int *x,bool type)
{
	for(int i=0,j=0;i<len;i++)
	{
		if(i<j)swap(x[i],x[j]);
		for(int k=len>>1;(j^=k)<k;k>>=1);
	}
	for(int l=2;l<=len;l<<=1)
	{
		int wn=qpow(type==1?G:Gi,(mod-1)/len);
		for(int k=0;k<len;k+=l)
		{
			int h_l=l>>1;
			for(int i=0,w=1;i<h_l;i++,w=mul(w,wn))
			{
				int a=x[i+k],b=mul(x[i+k+h_l],w);
				x[k+i]=add(a,b);
				x[k+i+h_l]=sub(a,b);
			}
		}
	}
}
signed main()
{
	int n=read(),m=read();
	for(int i=0;i<=n;i++)f[i]=read();
	for(int i=0;i<=m;i++)g[i]=read();
	int loglen=ceil(log2(n+m));
	len=1<<loglen;
	ntt(f,1);
	ntt(g,1);
	for(int i=0;i<len;i++)f[i]=mul(f[i],g[i]);
	ntt(f,0);
	int inv_n=qpow(len,mod-2);
	for(int i=0;i<=n+m;i++)
	printf("%lld ",mul(inv_n,f[i]));
	return 0;
}
2022/2/1 13:19
加载中...