```cpp
// NTT
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3000010;
const ll mod = 998244353, g = 114514, invg = 137043501;
ll fa[N], fb[N];
int n, m, k, rgt[N];
char a[N], b[N];
ll power (ll a, ll b, ll p) {
return b == 0? 1: (b & 1? a: 1) * power (a * a % p, b >> 1, p) % p;
}
void dft (ll* a, int n, int inv) {
for (int i = 0; i < n; i++) {
if (i < rgt[i]) {
swap (a[i], a[rgt[i]]);
}
}
for (int mid = 1; mid < n; mid <<= 1) {
ll wn = power (inv == 1? g: invg, (mod - 1) / (mid << 1), mod);
for (int i = 0; i < n; i += mid << 1) {
ll w = 1;
for (int j = 0; j < mid; j++) {
ll x = a[i + j], y = w * a[i + j + mid] % mod;
a[i + j] = (x + y) % mod;
a[i + j + mid] = (x - y + mod) % mod;
(w *= wn) %= mod;
}
}
}
if (inv == -1) {
for (int i = 0; i < n; i++) {
a[i] /= n;
}
}
}
int main () {
scanf ("%s%s", a, b);
n = strlen (a + 1);
m = strlen (b + 1);
for (; (1 << k) <= n + m; k++);
for (int i = 0; i < (1 << k); i++) {
rgt[i] = (rgt[i >> 1] >> 1) | ((i & 1) << (k - 1));
}
for (int i = 0; i <= n; i++) {
fa[i] = a[n - i] - '0';
}
for (int i = 0; i <= m; i++) {
fb[i] = b[m - i] - '0';
}
dft (fa, 1 << k, 1);
dft (fb, 1 << k, 1);
for (int i = 0; i < (1 << k); i++) {
(fa[i] *= fb[i]) %= mod;
}
dft (fa, 1 << k, -1);
int d = (1 << k) - 1;
for (int i = 0, c = 0; i <= d; i++) {
fa[i] += c;
c = fa[i] / 10;
fa[i] %= 10;
}
for (; fa[d - 1] == 0; d--);
for (int i = d - 1; i >= 0; i--) {
printf ("%d", fa[i]);
}
printf ("\n");
return 0;
}
```
by denominator @ 2023-08-04 15:03:32
没问题个鬼,复制错代码了 qwq。
此贴结。验证码回文的 mddm。
by denominator @ 2023-08-04 15:31:32