題面
題目傳送門
解法
題如其名……
不妨將多項式的\(x^i\)變成\(10^i\)，然后就是一個比較簡單的FFT了
md讀進來的是一個字符串，并且要倒序
最后注意進位問題
時間復雜度：\(O(n\ log\ n)\)
代碼
#include <bits/stdc++.h>
#define N 1 << 18
using namespace std;
template <typename node> void read(node &x) {x = 0; int f = 1; char c = getchar();while (!isdigit(c)) {if (c == '-') f = -1; c = getchar();}while (isdigit(c)) x = x * 10 + c - '0', c = getchar(); x *= f;
}
const double pi = acos(-1);
struct Complex {double x, y;Complex (double tx = 0, double ty = 0) {x = tx, y = ty;}
} a[N], b[N];
char s1[N], s2[N];
int ans[N], rev[N];
Complex operator + (Complex a, Complex b) {return (Complex) {a.x + b.x, a.y + b.y};}
Complex operator - (Complex a, Complex b) {return (Complex) {a.x - b.x, a.y - b.y};}
Complex operator * (Complex a, Complex b) {return (Complex) {a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x};}
void getrev(int l) {for (int i = 0; i < (1 << l); i++)rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << l - 1);
}
void FFT(Complex *a, int n, int key) {for (int i = 0; i < n; i++)if (i < rev[i]) swap(a[i], a[rev[i]]);for (int i = 1; i < n; i <<= 1) {Complex wn(cos(pi / i), key * sin(pi / i));for (int r = i << 1, j = 0; j < n; j += r) {Complex w(1, 0);for (int k = 0; k < i; k++, w = w * wn) {Complex x = a[j + k], y = w * a[i + j + k];a[j + k] = x + y, a[i + j + k] = x - y;}}}if (key == -1)for (int i = 0; i < n; i++) a[i].x /= n;
}
int main() {int n; read(n);scanf(" %s %s", s1, s2);for (int i = 0; i < n; i++)a[n - i - 1].x = s1[i] - '0', b[n - i - 1].x = s2[i] - '0';int len = 1, l = 0;while (len <= 2 * n - 2) len <<= 1, l++;getrev(l); FFT(a, len, 1), FFT(b, len, 1);for (int i = 0; i <= len; i++) a[i] = a[i] * b[i];FFT(a, len, -1);for (int i = 0; i <= len; i++) ans[i] = (int)(a[i].x + 0.5);for (int i = 0; i <= len; i++)ans[i + 1] += ans[i] / 10, ans[i] %= 10;while (len > 0 && ans[len] == 0) len--;for (int i = len; i >= 0; i--) cout << ans[i]; cout << "\n";return 0;
}
)
