代码

//by immotalCO
//just a test

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cassert>
#include <cmath>
#include <iostream>
using namespace std;
#define RG register
#define IL inline
//#define IL __inline__ __attribute__((always_inline))
#define For(i, a, b) for(RG int i = a, ___u = b; i <= ___u; ++i)
#define Dor(i, a, b) for(RG int i = b, ___d = a; i >= ___d; --i)
#define Rep(i, a, b) for(RG int i = a, ___u = b; i != ___u; ++i)
#define dmin(a, b) ((a) < (b) ? (a) : (b))
#define dmax(a, b) ((a) > (b) ? (a) : (b))
#define cmin(a, b) ((a) > (b) ? (a) = (b) : 1)
#define cmax(a, b) ((a) < (b) ? (a) = (b) : 1)
#define ddel(a, b) ((a) > (b) ? (a) - (b) : (b) - (a))
#define dabs(i) ((i) > 0 ? (i) : -(i))
typedef long long ll;
typedef unsigned uint;
#define constexpr

#include <bitset>

namespace pb_ds
{   
	namespace io
	{
		const int MaxBuff = 1 << 15;
		const int Output = 1 << 23;
		char B[MaxBuff], *S = B, *T = B;
		//#define getc() getchar()
		#define getc() ((S == T) && (T = (S = B) + fread(B, 1, MaxBuff, stdin), S == T) ? 0 : *S++)
		char Out[Output], *iter = Out;
	}

	const int MaxN = 1 << 18;
	
	template<class Type> IL Type read()
	{
		using namespace io;
		RG char ch; RG Type ans = 0; RG bool neg = 0;
		while(ch = getc(), (ch < '0' || ch > '9') && ch != '-')     ;
		ch == '-' ? neg = 1 : ans = ch - '0';
		while(ch = getc(), '0' <= ch && ch <= '9') ans = ans * 10 + ch - '0';
		return neg ? -ans : ans;
	}
	IL int gets(RG char *s)
	{
		using namespace io;
		RG char *t = s, ch;
		while(ch = getc(), ch == ' ' || ch == '\n' || ch == '\r')
			;
		*t++ = ch;
		while(ch = getc(), ch && ch != ' ' && ch != '\n' && ch != '\r')
			*t++ = ch;
		*t = 0;
		return t - s;
	}
	template<class Type> IL void Print(RG Type x, RG char ch = '\n')
	{
		using namespace io;
		if(!x) *iter++ = '0';
		else
		{
			if(x < 0) *iter++ = '-', x = -x;
			static int s[100]; RG int t = 0;
			while(x) s[++t] = x % 10, x /= 10;
			while(t) *iter++ = '0' + s[t--];
		}
		ch ? *iter++ = ch : 0;
	}
	
	struct Complex
	{
		double x, y;
		IL constexpr Complex operator + (RG const Complex& b) const
		{
			return (Complex) {x + b.x, y + b.y};
		}
		IL void operator += (RG const Complex& b)
		{
			x += b.x, y += b.y;
		}
		IL constexpr  Complex operator - (RG const Complex& b) const
		{
			return (Complex) {x - b.x, y - b.y};
		}
		IL constexpr  Complex operator * (RG const Complex& b) const
		{
			return (Complex) {x * b.x - y * b.y, x * b.y + y * b.x};
		}
		IL void operator *= (RG const double b)
		{
			x *= b, y *= b;
		}
		IL constexpr Complex conj()
		{
			return (Complex) {x, -y};
		}
	} w[MaxN];

	IL void init(RG int n)
	{
		static int N;
		if(n <= N) return; N = n;
		RG double ang;
		RG const double fac = 2 * acos(-1) / n;
		RG const int half = n >> 1;
		Rep(i, 0, half)
		{
			ang = i * fac;
			w[i + half] = (Complex) {cos(ang), sin(ang)};
		}
		Dor(i, 0, half - 1)
			w[i] = w[i << 1];
	}

	IL void DFT(RG int n, RG Complex *a, RG Complex *w)
	{
		RG int i, j, p, m, l;
		RG const int half = n >> 1;
		RG Complex tmp;
		for(i = 0, j = 0; i != n; ++i)
		{
			if(i < j) tmp = a[i], a[i] = a[j], a[j] = tmp;
			for(l = half; (j ^= l) < l; l >>= 1)
				;
		}
		RG Complex tmp0, tmp1, tmp2, tmp3, tmp4, tmp5, tmp6, tmp7, *wm, *ai, *ami;
		#define work(j, tmp) {tmp = ami[j] * wm[j]; ami[j] = ai[j] - tmp; ai[j] += tmp;}
		for(p = 2, m = 1; m != n; p = (m = p) << 1)
		{
			wm = w + m;
			#define DEF ai = a + i; ami = a + i + m;
			if(m < 8) for(i = 0; i != n; i += p) 
			{
				DEF
				for(j = 0; j != m; ++j) work(j, tmp)
			}
			else for(i = 0; i != n; i += p)
			{
				DEF
				for(j = 0; j != m; j += 8)
				{
					work(j,		tmp0)
					work(j + 1,	tmp1)
					work(j + 2,	tmp2)
					work(j + 3,	tmp3)
					work(j + 4,	tmp4)
					work(j + 5,	tmp5)
					work(j + 6,	tmp6)
					work(j + 7,	tmp7)
				}
			}
		}
	}
	const double pi = acos(-1);
	IL void FFT_conv(RG int _n, RG const int *x, RG const int *y, RG ll *ans)
	{
		static Complex a[MaxN], b[MaxN], c[MaxN];
		RG int i, j, N = _n >> 1;
		init(N);
		for(i = 0; i != N; ++i) 
		{
			(i << 1) < _n 
				? (a[i].x = x[i << 1], 		b[i].x = y[i << 1])
				: (a[i].x = b[i].x = 0.0);
			(i << 1 | 1) < _n
				? (a[i].y = x[i << 1 | 1], 	b[i].y = y[i << 1 | 1])
				: (a[i].y = b[i].y = 0.0);
		}
		DFT(N, a, w), DFT(N, b, w);
		RG Complex C0 = (Complex) {4.0, 0.0};
		RG Complex C1 = (Complex) {1.0, 0.0};
		RG Complex C2 = (Complex) {0, 0.25};
		#define Conj(x) (x).conj()
		RG Complex w = C1; RG int H = N >> 1;
		for(i = 0; i != N; ++i)
		{
			//w=(Complex){cos(2*i*pi/N),sin(2*i*pi/N)};
			if(i < H) w = pb_ds::w[H + i];
			else if(i == H) w = (Complex) {-1.0, 0};
			else w = pb_ds::w[H + N - i], w.y = -w.y;
			j = (N - i) & (N - 1);
			c[i ? N - i : 0] = (C0 * Conj(a[j] * b[j]) - (Conj(a[j]) - a[i]) * (Conj(b[j]) - b[i]) * (w + C1)) * C2;
		}
		DFT(N, c, pb_ds::w);
		Rep(i, 0, N)
		{
			ans[i << 1] 	= (ll) (c[i].y / N + 0.5);// % mod;
			ans[i << 1 | 1] = (ll) (c[i].x / N + 0.5);// % mod;
		}
	}
	
	int a[MaxN], b[MaxN];
	ll c[MaxN];

	char inp[MaxN];

	const int B = 4;
	const int Mod = 10000;

	IL int Export(RG char *s, RG int M, RG int *out)
	{
		RG int N = 0, x, v;
		while(M)
		{
			x = 0; v = 1;
			Rep(__, 0, B) M ? x += v * (s[--M] - '0'), v *= 10 : 0; 
			out[N++] = x;
		}
		return N;
	}

	IL void main()
	{
		
		RG int N = Export(inp, gets(inp), a);
		RG int M = Export(inp, gets(inp), b);
		RG int T = 1; while(T < N || T < M) T <<= 1;
		FFT_conv(T << 1, a, b, c);		

		RG ll tmp;
		RG int K = 0, KK = T << 1;
		while(!c[KK - 1]) --KK;
		while(K < KK || tmp)
		{
			tmp = c[K] / Mod;
			c[  K] -= Mod * tmp;
			c[++K] += tmp;
		}
		Print(c[--K], 0);
		int x;
		while(K--)
		{
			x = c[K];
			*io::iter++ = x / 1000			+ '0';
			*io::iter++ = x / 100 	% 10	+ '0';
			*io::iter++ = x / 10 	% 10	+ '0';
			*io::iter++ = x			% 10	+ '0';
		}
		*io::iter++ = '\n';
		using namespace io;
		fwrite(Out, 1, iter - Out, stdout);
	}
}

int main()
{
	#define FILE "dev"
	//freopen(FILE ".in", "r", stdin), freopen(FILE ".out", "w", stdout);
	pb_ds::main();
	fclose(stdin), fclose(stdout);  
}

评测结果