提交记录 17262


用户 题目 状态 得分 用时 内存 语言 代码长度
LinZhengyu 1002i. 【模板题】多项式乘法 Accepted 100 59.459 ms 7220 KB C++ 1.73 KB
提交时间 评测时间
2022-01-11 20:36:48 2022-01-11 20:36:52
#include<cstdio>
#include<algorithm>
#include<cassert>
#include<ctime>
#include<vector>
const int N=1e6,M=1<<21,P=998244353,G=3;

inline int upb(int x){--x,x|=x>>1,x|=x>>2,x|=x>>4,x|=x>>8,x|=x>>16;return x+1;}
inline int ksm(int x,int y){int z=1;for(;y;x=1ll*x*x%P,y>>=1)if(y&1)z=1ll*z*x%P;return z;}
inline int inv(int x){return ksm(x,P-2);}

int n,m; 

std::vector<int>p1,p2,ans;
namespace Poly
{
	int og[M+5];
	inline void init(int l)
	{
		og[1]=1;
		for(int i=2;i<l;i<<=1)
			for(int j=i,e=ksm(G,(P-1)/(i*2));j<i*2;j+=2)
				og[j]=og[j>>1],og[j|1]=1ll*og[j]*e%P;
	}
	inline void dif(std::vector<int>&a)
	{
		int l=a.size();
		for(int i=l>>1;i;i>>=1)for(int j=0;j<l;j+=i*2)for(int k=0;k<i;++k)
		{
			int x=a[j|k],y=a[j|i|k];
			a[j|k]=(x+y)%P,a[j|i|k]=1ll*(x+P-y)*og[i|k]%P;
		}
	}
	inline void idft(std::vector<int>&a)
	{
		int l=a.size();
		for(int i=1;i<l;i<<=1)for(int j=0;j<l;j+=i*2)for(int k=0;k<i;++k)
		{
			int x=a[j|k],y=1ll*a[j|i|k]*og[i|k]%P;
			a[j|k]=(x+y)%P,a[j|i|k]=(x+P-y)%P;
		}
		for(int i=0,z=P-(P-1)/l;i<l;++i)a[i]=1ll*a[i]*z%P;
		for(int i=1;i<l-i;++i)std::swap(a[i],a[l-i]);
	}
	inline void mul(std::vector<int>&a,std::vector<int>&b,std::vector<int>&c)
	{
		int la=a.size(),lb=b.size(),l=upb(la+lb-1);
		
		std::vector<int>ca=a,cb=b;
		
		a.resize(l),b.resize(l);
		dif(a),dif(b);
		
		c.resize(l);
		for(int i=0;i<l;++i)c[i]=1ll*a[i]*b[i]%P;
		idft(c);
		c.resize(la+lb-1);
		
		std::swap(a,ca),std::swap(b,cb);
	}
};

int main()
{
//	freopen("ntt.in","r",stdin),freopen("ntt.out","w",stdout);
	
	scanf("%d%d",&n,&m);
	p1.resize(n+1),p2.resize(m+1);
	for(int i=0;i<=n;++i)scanf("%d",&p1[i]);
	for(int i=0;i<=m;++i)scanf("%d",&p2[i]);
	
	Poly::init(upb(n+m+1));
	Poly::mul(p1,p2,ans);
	
	for(int x:ans)printf("%d ",x);
	puts("");

	return 0;
}

CompilationN/AN/ACompile OKScore: N/A

Subtask #1 Testcase #114.82 us28 KBAcceptedScore: 0

Subtask #1 Testcase #259.059 ms6 MB + 996 KBAcceptedScore: 0

Subtask #1 Testcase #327.129 ms3 MB + 72 KBAcceptedScore: 100

Subtask #1 Testcase #427.149 ms3 MB + 60 KBAcceptedScore: 0

Subtask #1 Testcase #516.3 us28 KBAcceptedScore: 0

Subtask #1 Testcase #615.26 us28 KBAcceptedScore: 0

Subtask #1 Testcase #715.44 us28 KBAcceptedScore: 0

Subtask #1 Testcase #853.24 ms6 MB + 460 KBAcceptedScore: 0

Subtask #1 Testcase #953.29 ms6 MB + 460 KBAcceptedScore: 0

Subtask #1 Testcase #1047.481 ms5 MB + 944 KBAcceptedScore: 0

Subtask #1 Testcase #1159.401 ms7 MB + 52 KBAcceptedScore: 0

Subtask #1 Testcase #1259.459 ms5 MB + 956 KBAcceptedScore: 0

Subtask #1 Testcase #1313.77 us28 KBAcceptedScore: 0


Judge Duck Online | 评测鸭在线
Server Time: 2022-01-29 06:43:04 | Loaded in 1 ms | Server Status
个人娱乐项目,仅供学习交流使用