提交记录 16175


用户 题目 状态 得分 用时 内存 语言 代码长度
OIerwanhong 1002. 测测你的多项式乘法 Accepted 100 256.27 ms 48808 KB C++11 2.15 KB
提交时间 评测时间
2021-04-16 17:21:45 2021-04-16 17:21:47
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
typedef long long ll;
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 int MAXN = 2097211,mod=998244353;
ll Qpow(ll a,ll p)
{
	ll res=1;
	while(p){if(p&1)res=res*a%mod;a=a*a%mod,p>>=1;}
	return res;
}
inline int S(int x){return x<mod?x:x-mod;}
inline int D(int x){return x<0?x+mod:x;}
ll RT[MAXN];
int f[MAXN],g[MAXN];
int init(int n)
{
	int len=1;
	while(len<=n)len<<=1;
	for(int i=1;i<len;i<<=1)
	{
		ll R(Qpow(3,(mod-1)/(i<<1)));
		RT[i]=1;
		for(int j=1;j<i;++j)RT[i+j]=RT[i+j-1]*R%mod;
	}
	return len;
}
int status[MAXN];
void DFT(int* a,int len)
{
	for(int i=0;i<len;++i)
		if(status[i]>i)std::swap(a[i],a[status[i]]);
	for(int cur=1;cur<4&&cur<len;cur<<=1)
		for(int j=0;j<len;j+=cur<<1)
			for(int k=0;k<cur;++k)
			{
				int x=a[j+k],y=a[j+cur+k]*RT[cur+k]%mod;
				a[j+k]=S(x+y),a[j+cur+k]=D(x-y);
			}
	for(int cur=4;cur<len;cur<<=1)
		for(int j=0;j<len;j+=cur<<1)
			for(int k=0;k<cur;k+=4)
			{
				int y=a[j+cur+k]*RT[cur+k]%mod;
				a[j+cur+k]=D(a[j+k]-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]=D(a[j+k+1]-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]=D(a[j+k+2]-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]=D(a[j+k+3]-y),a[j+k+3]=S(a[j+k+3]+y);
			}
}
void IDFT(int* a,int len)
{
	std::reverse(a+1,a+len);
	DFT(a,len);
	ll inv=Qpow(len,mod-2);
	for(int i=0;i<len;++i)a[i]=a[i]*inv%mod;
}
void poly_multiply(unsigned *a, int n, unsigned *b, int m, unsigned *c)
{
	int len=init(n+m);
	for(int i=0;i<=n;++i)f[i]=a[i];
	for(int i=0;i<=m;++i)g[i]=b[i];
	for(int i=0;i<len;++i)
		status[i]=(status[i>>1]>>1)|((i&1)?len>>1:0);
	DFT(f,len),DFT(g,len);
	for(int i=0;i<len;++i)f[i]=ll(f[i])*g[i]%mod;
	IDFT(f,len);
	for(int i=0;i<=n+m;++i)c[i]=f[i];
}


CompilationN/AN/ACompile OKScore: N/A

Testcase #1256.27 ms47 MB + 680 KBAcceptedScore: 100


Judge Duck Online | 评测鸭在线
Server Time: 2024-11-23 05:15:51 | Loaded in 1 ms | Server Status
个人娱乐项目,仅供学习交流使用 | 捐赠