记录编号	397250	评测结果	AAAAAAAAAA
题目名称	超强的乘法问题	最终得分	100
用户昵称	‎MistyEye	是否通过	通过
代码语言	C++	运行时间	2.131 s
提交时间	2017-04-19 21:15:22	内存使用	22.31 MiB

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn = (1<<20)+1;
const int mod = 7*17<<23|1, phi = mod-1, G = 3;
int Pow(int x, int y, int m = mod) {
	int ans = 1;
	for(; y; y>>=1, x=1LL*x*x%m)
		if(y&1) ans = 1LL*ans*x%m;
	return ans;
}
int a[maxn], b[maxn], c[maxn], rev[maxn];
void NTT_init(int n) {
	int l = 0; while((1<<l)<n) ++l; --l;
	for(int i=0; i<n; ++i)
		rev[i] = rev[i>>1]>>1|((i&1)<<l);
}
void NTT(int *a, int n, int op) {
	for(int i=0; i<n; ++i) if(rev[i]>i) swap(a[i], a[rev[i]]);
	for(int k=2; k<=n; k<<=1) {
		long long wn = Pow(G, (op*phi/k+phi)%phi);
		for(int j=0; j<n; j+=k) {
			long long w = 1;
			for(int i=0; i<(k>>1); ++i, w=w*wn%mod) {
				long long t = a[i+j+(k>>1)]*w%mod;
				a[i+j+(k>>1)] = (a[i+j]-t+mod)%mod;
				a[i+j] = (a[i+j]+t)%mod;
			}
		}
	}
	if(op==-1) {
		long long inv = Pow(n, mod-2);
		for(int i=0; i<n; ++i) a[i] = a[i]*inv%mod;
	}
}

int main() {
	freopen("bettermul.in","r",stdin);
	freopen("bettermul.out","w",stdout);
	static char s1[maxn], s2[maxn];
	static int n1, n2, m, ans[maxn];
	scanf("%s%s", s1, s2);
	n1 = strlen(s1);
	n2 = strlen(s2);
	for(int i=0; i<n1; ++i) a[i] = s1[n1-i-1]-'0';
	for(int i=0; i<n2; ++i) b[i] = s2[n2-i-1]-'0';
	m = n1+n2;
	int n; for(n=1; n<m; n<<=1);
	NTT_init(n);
	NTT(a, n, 1); NTT(b, n, 1);
	for(int i=0; i<n; ++i) c[i] = 1LL*a[i]*b[i]%mod;
	NTT(c, n, -1);
	for(int i=0; i<m; ++i) ans[i] = c[i];
	for(int i=0; i<m; ++i) ans[i+1] += ans[i]/10, ans[i] %= 10;
	for(; ans[m]; ++m) ans[m+1] += ans[m]/10, ans[m] %= 10;
	for(; m>1 && !ans[m-1]; --m);
	for(int i=m-1; ~i; --i) printf("%d", ans[i]); puts("");
	getchar(), getchar();
	return 0;
}