提交记录 7235


用户 题目 状态 得分 用时 内存 语言 代码长度
ilnil 1004. 【模板题】高精度乘法 Accepted 100 889.56 ms 120212 KB C++ 1.57 KB
提交时间 评测时间
2019-01-15 22:11:07 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++)
#define db double
using namespace std;
const int N=1e6+5,M=(1<<21)+1,mo=998244353,P=(1<<21)+1;
const db pi=acos(-1);
char in[P],*is=in,*it=in,out[P],*os=out,*ot=out+P-1,o[20],c;
int n,m,Q;
int h[M],aa[M];
db ny;
struct no{
	db x,y;
	no(){x=y=0;}
	no(const db &_x,const db &_y){x=_x;y=_y;}
	no operator+(const no &z){return no(x+z.x,y+z.y);}
	no operator-(const no &z){return no(x-z.x,y-z.y);}
	no operator*(const no &z){return no(x*z.x-y*z.y,x*z.y+y*z.x);}
}a[M],b[M],w[M];
void dft(no *a){
	fo(i,1,Q)if(i<h[i])swap(a[i],a[h[i]]);
	no A;
	for(int i=2,j,m,k,g=Q>>1;m=i>>1,i<=Q;g>>=1,i<<=1)for(j=0;j<Q;j+=i){
		no *p=w,*l=a+j,*r=a+j+m;
		for(k=0;k<m;k++){
			A=*p* *r;
			*r=*l-A;
			*l=*l+A;
			l++,r++,p+=g;
		}
	}
}
int main(){
	for(;(c=gc())<='9'&&c>='0';)a[++n].x=c-48;
	for(;(c=gc())<'0'||c>'9';);
	for(;b[++m].x=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=1./Q;
	fo(i,0,Q)w[i]=no(cos(pi*2*i/Q),sin(pi*2*i/Q)),h[i]=(h[i>>1]>>1)|(i&1)*(Q>>1);
	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]=a[i]*b[i];
	fo(i,1,Q>>1)swap(a[i],a[Q-i]);
	dft(a);
	int y=0;
	n+=m-2;
	fo(i,0,n){
		aa[i]=(int)(a[i].x*ny+0.5)+y;
		y=aa[i]/10;
		aa[i]=aa[i]%10;
	}
	if(y)aa[++n]=y;
	fd(i,0,n)put(aa[i]+48);
	flush();
}

CompilationN/AN/ACompile OKScore: N/A

Testcase #1889.56 ms117 MB + 404 KBAcceptedScore: 100


Judge Duck Online | 评测鸭在线
Server Time: 2026-04-08 19:30:16 | Loaded in 1 ms | Server Status
个人娱乐项目,仅供学习交流使用 | 捐赠