记录编号	538249	评测结果	AAAAAAAAAA
题目名称	超强的乘法问题	最终得分	100
用户昵称	神利·代目	是否通过	通过
代码语言	C++	运行时间	0.521 s
提交时间	2019-07-23 19:19:29	内存使用	17.75 MiB

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define P 998244353
#define g 3
#define ll long long

int mypow(int x, int y) {
	int res = 1;
	while (y) {
		if (y & 1)res = 1ll * res * x % P;
		y >>= 1;
		x = 1ll * x * x % P;
	}
	return res;
}

void NTT(int* o, int n, bool op) {
	for (int i = 0, j = 0; i < n; ++i) {
		if (i > j)std::swap(o[i], o[j]);
		for (int k = n >> 1; (j ^= k) < k; k >>= 1);
	}
	for (int i = 2, y; i <= n; i <<= 1)
		for (ll wn = mypow(g, op ? (P - 1) / i : P - 1 - (P - 1) / i), j = 0; j < n; j += i)
			for (ll w = 1, k = 0, p = i >> 1; k < p; ++k, w = w * wn % P)
				y = w * o[j + k + p] % P, o[j + k + p] = (o[j + k] - y + P) % P, o[j + k] = (o[j + k] + y) % P;
	if (!op) {
		ll invn = mypow(n, P - 2);
		for (int i = 0; i < n; ++i)o[i] = invn * o[i] % P;
	}
}

int lena, lenb;
char a[1000010], b[1000010];
int A[1000010], B[1000010], C[1000010];
int main() {
	freopen("bettermul.in", "r", stdin);
	freopen("bettermul.out", "w", stdout);
	scanf("%s%s", a, b);
	lena = strlen(a);
	lenb = strlen(b);
	for (int i = 0; i < lena; ++i)
		A[i] = a[lena - i - 1] - '0';
	for (int i = 0; i < lenb; ++i)
		B[i] = b[lenb - i - 1] - '0';
	int len = 1;
	while ((len >> 1) < lena || (len >> 1) < lenb)len <<= 1;
	NTT(A, len, 1);
	NTT(B, len, 1);
	for (int i = 0; i < len; ++i)
		C[i] = 1ll * A[i] * B[i] % P;
	NTT(C, len, 0);
	for(int i=0;i<len;++i)
		if (C[i]) {
			C[i + 1] += C[i] / 10;
			C[i] %= 10;

		}
	bool flag = 0;
	for(int i=len-1;i>=0;--i)
		if(C[i]||flag){
			flag = 1;
			putchar(C[i] | 48);
		}
}
/*
1
10
*/