提交记录 7237


用户 题目 状态 得分 用时 内存 语言 代码长度
ilnil 1004. 【模板题】高精度乘法 Accepted 100 313.754 ms 34576 KB C++ 1.35 KB
提交时间 评测时间
2019-01-16 17:08:56 2020-08-01 01:01:42
#include<bits/stdc++.h>
#define fo(i,a,b)for(int i=a,_e=b;i<=_e;i++)
#define fd(i,a,b)for(int i=b,_e=a;i>=_e;i--)
#define ll long long
#define flush()(fwrite(out,1,os-out,stdout),os=out)
#define put(x)(*os++=x,os==ot?flush():0)
#define gc()(it==is?it=(is=in)+fread(in,1,P,stdin),(it==is?EOF:*is++):*is++)
using namespace std;
const int N=1e6+5,M=(1<<21)+1,mo=998244353,P=(1<<21)+1;
char in[P],*is=in,*it=in,out[P],*os=out,*ot=out+P-1,o[20],c;
int n,m,Q;
int a[M],b[M],w[M],h[M],ny;
ll A;
int ksm(int x,int y){
	int t=1;
	for(;y;y>>=1,x=(ll)x*x%mo)if(y&1)t=(ll)t*x%mo;
	return t;
}
void dft(int *a){
	fo(i,1,Q)if(h[i]>i)swap(a[i],a[h[i]]);ll A;
	for(int i=2,m,j,k,g,p,*l,*r;m=i>>1,i<=Q;i<<=1){
		g=ksm(3,(mo-1)/i);w[0]=1;
		for(k=1;k<m;k++)w[k]=(ll)w[k-1]*g%mo;
		for(j=0;j<Q;j+=i){
			l=a+j;r=l+m;
			for(k=0;k<m;l++,r++,k++)A=(ll)w[k]* *r,*r=(-A+*l)%mo,*l=(A+*l)%mo;
		}
	}
}
int main(){
	for(;(c=gc())<='9'&&c>='0';)a[++n]=c-48;
	for(;(c=gc())<'0'||c>'9';);
	for(;b[++m]=c-48,(c=gc())<='9'&&c>='0';);
	fo(i,0,n>>1)swap(a[i],a[n-i]);
	fo(i,0,m>>1)swap(b[i],b[m-i]);
	for(Q=1;Q<=n+m;Q<<=1);
	ny=ksm(Q,mo-2);
	fo(i,1,Q)h[i]=(h[i>>1]>>1)|(i&1?Q>>1:0);
	dft(a);dft(b);
	fo(i,0,Q)a[i]=(ll)a[i]*b[i]%mo;
	fo(i,1,Q>>1)swap(a[i],a[Q-i]);
	dft(a);
	ll y=0;
	n+=m-2;
	fo(i,0,n){
		a[i]=(ll)(a[i]+mo)*ny%mo+y;
		y=a[i]/10;
		a[i]=a[i]%10;
	}
	if(y)a[++n]=y;
	fd(i,0,n)put(a[i]+48);
	flush();
}

CompilationN/AN/ACompile OKScore: N/A

Testcase #1313.754 ms33 MB + 784 KBAcceptedScore: 100


Judge Duck Online | 评测鸭在线
Server Time: 2020-10-23 14:20:07 | Loaded in 1 ms | Server Status
个人娱乐项目,仅供学习交流使用