Hướng giải của NTT nhân đa thức

Nhớ rằng hướng dẫn giải này chỉ nên sử dụng khi bế tắc, và tuyệt đối không nên sao chép mã nguồn kèm theo. Hãy tôn trọng tác giả bài tập và người viết hướng dẫn giải.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.

Tác giả: kienadmin

Lời giải: NTT nhân đa thức

Phân tích

Dùng NTT với modulo \(998244353\) (gốc 3):

  1. Biến đổi NTT xuôi cả hai đa thức
  2. Nhân từng hệ số tương ứng
  3. Biến đổi NTT ngược

Độ phức tạp: \(O((n+m) \log (n+m))\).

Code mẫu C++

#include <bits/stdc++.h>
using namespace std;

const long long MOD = 998244353;
const long long G = 3;  // Can nguyen thuy

// Luy thua nhi phan
long long powerMod(long long a, long long b) {
    long long res = 1;
    a %= MOD;
    while (b > 0) {
        if (b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

// Bien doi NTT xuoi (inv=false) hoac nguoc (inv=true)
void ntt(vector<long long>& a, bool inv) {
    int n = a.size();

    // Sap xep lai cac he so theo bit-reversal
    for (int i = 1, j = 0; i < n; i++) {
        int bit = n >> 1;
        for (; j & bit; bit >>= 1) j ^= bit;
        j ^= bit;
        if (i < j) swap(a[i], a[j]);
    }

    // Bien doi tu duoi len
    for (int len = 2; len <= n; len <<= 1) {
        long long wlen = powerMod(G, (MOD - 1) / len);
        if (inv) wlen = powerMod(wlen, MOD - 2);

        for (int i = 0; i < n; i += len) {
            long long w = 1;
            for (int j = 0; j < len / 2; j++) {
                long long u = a[i + j];
                long long v = a[i + j + len / 2] * w % MOD;
                a[i + j] = (u + v) % MOD;
                a[i + j + len / 2] = (u - v + MOD) % MOD;
                w = w * wlen % MOD;
            }
        }
    }

    // Neu la bien doi nguoc, chia cho n
    if (inv) {
        long long inv_n = powerMod(n, MOD - 2);
        for (long long& x : a) x = x * inv_n % MOD;
    }
}

int main() {
    int n, m;
    cin >> n >> m;

    // Tim kich thuoc la luy thua cua 2
    int sz = 1;
    while (sz < n + m - 1) sz <<= 1;

    vector<long long> a(sz, 0), b(sz, 0);

    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < m; i++) cin >> b[i];

    // NTT xuoi
    ntt(a, false);
    ntt(b, false);

    // Nhan tung he so
    for (int i = 0; i < sz; i++) a[i] = a[i] * b[i] % MOD;

    // NTT nguoc
    ntt(a, true);

    // In ket qua
    for (int i = 0; i < n + m - 1; i++) {
        cout << a[i] << (i == n + m - 2 ? "\n" : " ");
    }

    return 0;
}

Nhận xét

Không có ý kiến tại thời điểm này.