提交记录 16138


用户 题目 状态 得分 用时 内存 语言 代码长度
zhoufangyuanPT 1002. 测测你的多项式乘法 Accepted 100 291.573 ms 56980 KB C++ 1.16 KB
提交时间 评测时间
2021-04-06 21:39:05 2021-04-06 21:39:08
#define p 998244353
#define g 3
long long ksm(long long x,long long k)
{
	long long s=1;
	while(k>0)
	{
		if(k&1)s=s*x%p;
		x=x*x%p;
		k>>=1;
	}
	return s;
}
struct poly
{
	long long a[2097152];
	void ntt(int);
}A,B;int len;
int r[2097152];
long long w[2097152];
inline long long plus(long long x,long long y){return x+y<p?x+y:x+y-p;}
inline long long jian(long long x,long long y){return x<y?x-y+p:x-y;}
void poly::ntt(int type)
{
	for(int i=0;i<len;i++)if(i<r[i])a[i]^=a[r[i]]^=a[i]^=a[r[i]];
	w[0]=1;
	for(int i=1;i<len;i<<=1)
	{
		long long wi=ksm(g,type*(p-1)/i/2+p-1);
		for(int j=i-2;j>=2;j-=2)w[j]=w[j>>1];
		for(int j=1;j<i;j+=2)w[j]=w[j-1]*wi%p;
		for(int j=0;j<len;j+=i<<1)
		{
			for(int k=0;k<i;k++)
			{
				long long ak=a[j+k],awk=w[k]*a[i+j+k]%p;
				a[j+k]=plus(ak,awk);a[i+j+k]=jian(ak,awk);
			}
		}
	}
}
void poly_multiply(unsigned *a,int n,unsigned *b,int m,unsigned *c)
{
	len=2097152;
	r[0]=0;
	for(int i=1;i<len;i++)r[i]=r[i>>1]>>1|(i&1)<<20;
	for(int i=0;i<=n;i++)A.a[i]=a[i];
	for(int i=0;i<=m;i++)B.a[i]=b[i];
	A.ntt(1);B.ntt(1);
	for(int i=0;i<len;i++)A.a[i]=A.a[i]*B.a[i]%p;
	A.ntt(-1);
	long long flen=ksm(len,p-2);
	for(int i=0;i<=n+m;i++)c[i]=A.a[i]*flen%p;
}

CompilationN/AN/ACompile OKScore: N/A

Testcase #1291.573 ms55 MB + 660 KBAcceptedScore: 100


Judge Duck Online | 评测鸭在线
Server Time: 2021-04-21 21:53:53 | Loaded in 0 ms | Server Status
个人娱乐项目,仅供学习交流使用