代码

//by AK Clin
//just a test

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath> 
using namespace std;
#define R register
#define cmax(_a,_b) (_a<(_b)?_a=(_b):0)
#define cmin(_a,_b) ((_b)<_a?_a=(_b):0)
#define dmax(_a,_b) ((_a)<(_b)?(_b):(_a))
#define dmin(_a,_b) ((_a)<(_b)?(_a):(_b))
#define maxn 1<<18
#define ll long long
template<class TT> void read(R TT &x) {
	x=0;R char ch=getchar();R bool f=0;
	while(ch<48||57<ch) f|=ch=='-',ch=getchar();
	while(47<ch&&ch<58) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	if(f) x=-x;
}
const double pi=acos(-1);
struct cp{
	double a,b;
	cp operator +(R const cp &o) {return (cp){a+o.a,b+o.b};}
	cp operator -(R const cp &o) {return (cp){a-o.a,b-o.b};}
	cp operator *(R const cp &o) {return (cp){a*o.a-b*o.b,a*o.b+b*o.a};}
	cp operator *(R const double &o) {return (cp){a*o,b*o};}
	cp operator !() const{return (cp){a,-b};}
} x[maxn],y[maxn],s[maxn],w[maxn];
void fft(R cp x[],R int k,int v) {
	for(R int i=0,j=0;i<k;++i) {
		if(j<i) swap(x[i],x[j]);
		for(R int l=k>>1;(j^=l)<l;l>>=1);
	}
	w[0]=(cp){1,0};
	for(R int i=2;i<=k;i<<=1) {
		cp g=(cp){cos(2*pi/i),v*sin(2*pi/i)};
		for(R int j=i>>1;j>=0;j-=2) w[j]=w[j>>1];
		for(R int j=1;j<i>>1;j+=2) w[j]=w[j-1]*g;
		for(R int j=0;j<k;j+=i) {
			cp *a=x+j,*b=a+(i>>1);
			for(R int l=0;l<i>>1;++l) {
				cp o=b[l]*w[l];
				b[l]=a[l]-o;
				a[l]=a[l]+o;
			}
		}
	}
	if(v==-1) {
		R double tmp=1.0/k;
		for(R int i=0;i<k;++i) x[i]=(cp){x[i].a*tmp,x[i].b*tmp};
	}
}
char s1[maxn],s2[maxn];
ll ans[maxn];
int K,n,m,maxt;
int main()
{
	scanf("%s%s",s1+4,s2+4);
	int n=strlen(s1+4),m=strlen(s2+4);
	for(R int i=4;i<n+4;++i) s1[i]^='0';
	for(R int i=n,j=0;i>0;i-=4,++j) ((j&1)?x[j>>1].b:x[j>>1].a)=s1[i]*1000+s1[i+1]*100+s1[i+2]*10+s1[i+3];
	for(R int i=4;i<m+4;++i) s2[i]^='0';
	for(R int i=m,j=0;i>0;i-=4,++j) ((j&1)?y[j>>1].b:y[j>>1].a)=s2[i]*1000+s2[i+1]*100+s2[i+2]*10+s2[i+3];
	for(K=1;K<n+m>>3;K<<=1);
	fft(x,K,1);fft(y,K,1);
	for(R int i=0;i<K;++i) {
		R int j=K-1&K-i;
		s[i]=(x[i]*y[i]*4-(x[i]-!x[j])*(y[i]-!y[j])*(((i&K>>1)?(cp){1,0}-w[i^K>>1]:w[i]+(cp){1,0})))*0.25;
	}
	fft(s,K,-1);
	for(R int i=0;i<K<<1;++i) ans[i]=((i&1)?s[i>>1].b:s[i>>1].a)+0.5;
	for(R int i=0;i<K<<1;++i) {
		ll tmp=ans[i]/10000;
		ans[i+1]+=tmp;
		ans[i]=ans[i]-tmp*10000;
		if(ans[i]) cmax(maxt,i);
	}
	printf("%lld",ans[maxt]);
	for(R int i=maxt-1;~i;--i) printf("%04lld",ans[i]);
	return 0;
}

评测结果