不知道为什么,样例会使第一位不输出,但是却能AC,不是很懂
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;
const int maxn = 3e6 + 5;
const ll mod = 998244353;
const ll G = 3;
const ll Gi = 332748118;
char s[maxn], t[maxn];
int limit = 1, L, r[maxn];
ll a[maxn], b[maxn];
ll fpm(ll a, ll k) {
ll res = 1;
while(k) {
if(k&1) res = res*a % mod;
a = a*a % mod;
k >>= 1;
}
return res;
}
void NTT(ll* A, bool type) {
for(int i = 0; i < limit; i++)
if(i < r[i]) swap(A[i], A[r[i]]);
for(int mid = 1; mid < limit; mid <<= 1) {
ll wn = fpm(type ? G : Gi, (mod-1)/(mid<<1));
for(int j = 0; j < limit; j += (mid<<1)) {
ll w = 1;
for(int k = 0; k < mid; k++, w = w*wn % mod) {
ll x = A[j+k], y = w*A[j+k+mid] % mod;
A[j+k] = (x+y) % mod;
A[j+k+mid] = (x-y + mod) % mod;
}
}
}
if(!type) {
ll inv = fpm(limit, mod-2);
for(int i = 0; i < limit; i++)
a[i] = a[i]*inv % mod;
}
}
int main() {
scanf("%s %s", s+1, t+1);
int n = strlen(s+1), m = strlen(t+1);
for(int i = n; i >= 1; i--) a[n-i] = s[i]-'0';
for(int i = m; i >= 1; i--) b[m-i] = t[i]-'0';
n--; m--;
while(limit <= n+m) limit <<= 1, L++;
for(int i = 0; i < limit; i++) r[i] = (r[i>>1]>>1) | ((i&1) << (L-1));
NTT(a, 1); NTT(b, 1);
for(int i = 0; i < limit; i++) a[i] = a[i]*b[i] % mod;
NTT(a, 0);
for(int i = 0; i < limit; i++)
if(a[i] >= 10) {
a[i+1] += a[i]/10;
a[i] %= 10;
}
n = limit-1;
while(a[n] == 0) n--;
for(int i = n; i >= 0; i--)
printf("%d", a[i]);
return 0;
}