提交记录 16179


用户 题目 状态 得分 用时 内存 语言 代码长度
OIerwanhong 1002. 测测你的多项式乘法 Accepted 100 262.088 ms 48808 KB C++11 2.13 KB
提交时间 评测时间
2021-04-16 18:17:46 2021-04-16 18:17:48
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
typedef unsigned long long ull;
typedef unsigned un;
/*
ll read()
{
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    return f*x;
}
using std::min;
using std::max;
template<typename T>bool umin(T& a,T t){if(a>t)return a=t,1;return 0;}
template<typename T>bool umax(T& a,T t){if(a<t)return a=t,1;return 0;}
ll abs(ll x){return x>0?x:-x;}
*/
const un MAXN = 2097152,mod=998244353;
ull Qpow(ull a,ull p)
{
	ull res=1;
	while(p){if(p&1)res=res*a%mod;a=a*a%mod,p>>=1;}
	return res;
}
inline un S(un x){return x<mod?x:x-mod;}
ull RT[MAXN];
un f[MAXN],g[MAXN];
un init(un n)
{
	un len=1;
	while(len<=n)len<<=1;
	for(un i=1;i<len;i<<=1)
	{
		ull R(Qpow(3,(mod-1)/(i<<1)));
		RT[i]=1;
		for(un j=1;j<i;++j)RT[i+j]=RT[i+j-1]*R%mod;
	}
	return len;
}
un status[MAXN];
void DFT(un* a,un len)
{
	for(un i=0;i<len;++i)
		if(status[i]>i)std::swap(a[i],a[status[i]]);
	for(un cur=1;cur<4&&cur<len;cur<<=1)
		for(un j=0;j<len;j+=cur<<1)
			for(un k=0;k<cur;++k)
			{
				un x=a[j+k],y=a[j+cur+k]*RT[cur+k]%mod;
				a[j+k]=S(x+y),a[j+cur+k]=S(x+mod-y);
			}
	for(un cur=4;cur<len;cur<<=1)
		for(un j=0;j<len;j+=cur<<1)
			for(un k=0;k<cur;k+=4)
			{
				un y=a[j+cur+k]*RT[cur+k]%mod;
				a[j+cur+k]=S(a[j+k]+mod-y),a[j+k]=S(a[j+k]+y);
				y=a[j+cur+k+1]*RT[cur+k+1]%mod;
				a[j+cur+k+1]=S(a[j+k+1]+mod-y),a[j+k+1]=S(a[j+k+1]+y);
				y=a[j+cur+k+2]*RT[cur+k+2]%mod;
				a[j+cur+k+2]=S(a[j+k+2]+mod-y),a[j+k+2]=S(a[j+k+2]+y);
				y=a[j+cur+k+3]*RT[cur+k+3]%mod;
				a[j+cur+k+3]=S(a[j+k+3]+mod-y),a[j+k+3]=S(a[j+k+3]+y);
			}
}
void IDFT(un* a,un len)
{
	std::reverse(a+1,a+len);
	DFT(a,len);
	ull inv=Qpow(len,mod-2);
	for(un i=0;i<len;++i)a[i]=a[i]*inv%mod;
}
void poly_multiply(unsigned *a, int n, unsigned *b, int m, unsigned *c)
{
	un len=init(n+m);
	for(un i=0;i<len;++i)
		status[i]=(status[i>>1]>>1)|((i&1)?len>>1:0);
	for(int i=0;i<=n;++i)f[i]=a[i];
	for(int i=0;i<=m;++i)g[i]=b[i];
	DFT(f,len),DFT(g,len);
	for(un i=0;i<len;++i)f[i]=ull(f[i])*g[i]%mod;
	IDFT(f,len);
	for(un i=0;i<=n+m;++i)c[i]=f[i];
}


CompilationN/AN/ACompile OKScore: N/A

Testcase #1262.088 ms47 MB + 680 KBAcceptedScore: 100


Judge Duck Online | 评测鸭在线
Server Time: 2024-03-28 17:49:48 | Loaded in 1 ms | Server Status
个人娱乐项目,仅供学习交流使用