提交记录 15422


用户 题目 状态 得分 用时 内存 语言 代码长度
asd_a 1002i. 【模板题】多项式乘法 Accepted 100 47.306 ms 10712 KB C++ 2.35 KB
提交时间 评测时间
2020-12-27 17:21:40 2020-12-27 17:21:44
#include<bits/stdc++.h>
#define ll long long
#define vci vector<int>
using namespace std;
const int mod=998244353;
const int N=1<<21|5;
const int gen=3;
inline int fsp(int x,int y){
	int ans=1;for(;y;y>>=1,x=1ll*x*x%mod)(y&1)&&(ans=1ll*ans*x%mod);
	return ans;
}namespace Math{
	int tr=0,tw=2,tv=2,rev[N],w[N],iv[N];
	inline void initrev(int x){
		tr=x;for(int i=0;i<x;i++)rev[i]=rev[i>>1]>>1|((i&1)?x>>1:0);
	}inline void initw(int x){(!w[1])&&(w[1]=1);
		for(;tw<x;tw<<=1){
			w[tw]=1;w[tw+1]=fsp(gen,mod/(tw<<1));
			for(int i=tw+2;i<(tw<<1);++i)w[i]=1ll*w[i-1]*w[tw+1]%mod;
		}
	}inline void initiv(int x){(!iv[1])&&(iv[1]=1);
		for(;tv<=x;++tv)iv[tv]=1ll*(mod-mod/tv)*iv[mod%tv]%mod;
	}inline int ginv(int x){
		(x<=1<<21)&&(initiv(x),0);
		return x<tv?iv[x]:fsp(x,mod-2);
	}inline void ntt(int* a,int lim,int fl=1){
		static unsigned ll A[N];initw(lim);
		(tr!=lim)&&(initrev(lim),0);
		for(int i=0;i<lim;i++)A[i]=a[rev[i]];
		for(int k=1;k<lim;k<<=1){
			if(k==1<<18)for(int i=0;i<lim;++i)A[i]%=mod;
			for(int j=0;j<lim;j+=k<<1)for(int i=j,t;i<j+k;++i)
				A[i+k]=A[i]+mod-(t=A[i+k]*w[i+k-j]%mod),A[i]+=t;
		}if(fl^1){reverse(A+1,A+lim);for(int i=0,niv=ginv(lim);i<lim;i++)a[i]=A[i]*niv%mod;}
		else for(int i=0;i<lim;i++)a[i]=A[i]%mod;
	}
}namespace Poly{
	using Math::ntt;
	int A[N];
	struct poly{
		vci f;poly(int x=0){f.clear();(x)&&(f.push_back(x),0);}
		poly(int *a,int n){f.resize(n);memcpy(f.data(),a,n<<2);}
		inline int operator [](int x)const{return x<f.size()?f[x]:0;}
		inline int& operator [](int x){return f.at(x);}
		inline int* data(){return f.data();}inline const int* data()const{return f.data();}
		inline int size()const{return f.size();}inline void resize(int x){return f.resize(x);}
		inline poly& operator *=(const poly& a){
			int lim=1;while(lim<size()+a.size()-1)lim<<=1;
			resize(lim);memcpy(A,a.data(),a.size()<<2);ntt(data(),lim);ntt(A,lim);
			for(int i=0;i<lim;i++)f[i]=1ll*f[i]*A[i]%mod;
			ntt(data(),lim,0);return *this;
		}inline poly operator *(const poly& a)const{poly b(*this);(b*=a).resize(size()+a.size()-1);return b;}
		inline void print(char ch=' ')const{
			for(int i=0;i<size();++i,putchar(ch))printf("%d",f[i]);
			putchar('\n');
		}
	};
}
using Poly::poly;
int n,m,a[N],b[N];
poly f;
int main(){
	scanf("%d%d",&n,&m);++n;++m;
	for(int i=0;i<n;i++)scanf("%d",a+i);
	for(int i=0;i<m;i++)scanf("%d",b+i);
	(poly(a,n)*poly(b,m)).print();
	return 0;
}

CompilationN/AN/ACompile OKScore: N/A

Subtask #1 Testcase #138.67 us64 KBAcceptedScore: 0

Subtask #1 Testcase #246.971 ms10 MB + 392 KBAcceptedScore: 100

Subtask #1 Testcase #320.435 ms4 MB + 612 KBAcceptedScore: 0

Subtask #1 Testcase #420.405 ms4 MB + 996 KBAcceptedScore: 0

Subtask #1 Testcase #540.99 us64 KBAcceptedScore: 0

Subtask #1 Testcase #639.97 us64 KBAcceptedScore: 0

Subtask #1 Testcase #739.65 us64 KBAcceptedScore: 0

Subtask #1 Testcase #842.056 ms9 MB + 748 KBAcceptedScore: 0

Subtask #1 Testcase #941.918 ms9 MB + 884 KBAcceptedScore: 0

Subtask #1 Testcase #1036.934 ms9 MB + 212 KBAcceptedScore: 0

Subtask #1 Testcase #1147.306 ms10 MB + 472 KBAcceptedScore: 0

Subtask #1 Testcase #1246.938 ms9 MB + 352 KBAcceptedScore: 0

Subtask #1 Testcase #1338.31 us64 KBAcceptedScore: 0


Judge Duck Online | 评测鸭在线
Server Time: 2025-05-04 12:29:41 | Loaded in 1 ms | Server Status
个人娱乐项目,仅供学习交流使用 | 捐赠