FFT và NTT: nhân đa thức nhanh

Nhân $123 \times 45$ trên giấy: nhân từng cặp chữ số, rồi gom các tích có cùng vị trí. Gom như vậy chính là tích chập $c_k = \sum_{i + j = k} a_i b_j$ , tức phép nhân hai đa thức. Hai số có nửa triệu chữ số thì $O(nm)$ phép nhân là quá nhiều.

FFT đổi đa thức sang dạng giá trị tại các căn đơn vị trong $O(n \log n)$ , nhân từng điểm, rồi đổi ngược. NTT làm đúng việc đó trên trường số nguyên tố, chính xác tuyệt đối. Rất nhiều bài đếm không có chữ “đa thức” trong đề: đếm cặp theo tổng, theo khoảng cách, so khớp xâu theo mọi độ dịch, đều là một tích chập.

Tích chập và NTT

Đa thức bậc nhỏ hơn $n$ được xác định bởi giá trị tại $n$ điểm. Nhân hai đa thức ở dạng giá trị chỉ là nhân từng điểm, $O(n)$ . Khó ở chỗ đổi qua lại giữa hệ số và giá trị: nếu làm thẳng thì tốn $O(n^2)$ .

Trong hình, ô $(i, j)$ là $a_i \cdot b_j$ và $c_k$ là tổng trên đường chéo $i + j = k$ . Kéo $k$ để xem từng đường chéo.

Tích chập là tổng các đường chéo.

Mẹo để đổi nhanh: chọn $n$ là lũy thừa của 2 và các điểm là lũy thừa của một căn đơn vị bậc $n$ $\omega$ . Chia đa thức thành phần hệ số chẵn và lẻ, $A(x) = A_0(x^2) + x A_1(x^2)$ . Vì $\omega^2$ là căn bậc $n/2$ , hai nửa là hai bài cùng dạng với kích thước một nửa. Phép “bướm”

A(\omega^j) = A_0(\omega^{2j}) + \omega^j A_1(\omega^{2j}), \quad A(\omega^{j + n/2}) = A_0(\omega^{2j}) - \omega^j A_1(\omega^{2j})

cho $O(n \log n)$ . Cài không đệ quy: đảo bit chỉ số để đưa hệ số về đúng thứ tự lá, rồi gộp từng tầng độ dài 2, 4, 8, …

Theo mô-đun $p = 998244353 = 119 \cdot 2^{23} + 1$ , căn nguyên thủy là 3, nên $3^{(p-1)/n}$ là căn đơn vị bậc $n$ với mọi $n$ là lũy thừa của 2 tới $2^{23}$ . Biến đổi ngược dùng căn nghịch đảo và chia cho $n$ . Để nhân, chọn $n$ là lũy thừa của 2 không nhỏ hơn $|a| + |b| - 1$ .

Hình dưới chạy NTT 8 điểm theo mô-đun 17 (căn nguyên thủy 3) để thấy các tầng: mỗi tầng ghép từng cặp bằng $u + v \cdot w$ và $u - v \cdot w$ .

Các tầng của phép biến đổi.

Ví dụTích chập mô-đun

Đề. Hai dãy dài tới $524288$ , hệ số theo mô-đun $998244353$ . In tích chập.

Lời giải. Tích chập có $n + m - 1$ hệ số, nên chọn độ dài sz là lũy thừa của 2 không nhỏ hơn số đó, đệm 0 cho hai dãy. Đệm đủ dài là bắt buộc: nếu sz nhỏ hơn $n + m - 1$ thì phần hệ số vượt quá sẽ cộng vòng về đầu dãy. NTT thuận đổi mỗi dãy sang dạng giá trị tại sz căn đơn vị; nhân từng điểm là nhân hai đa thức; NTT ngược đổi lại thành hệ số.

Bước 1: hoán vị đảo bit. j là i viết ngược các bit, cập nhật từ giá trị trước bằng phép “cộng 1 từ bên trái”: xóa các bit 1 cao nhất liên tiếp rồi bật bit 0 đầu tiên. Đổi chỗ khi i < j để mỗi cặp chỉ đổi một lần. Sau bước này các hệ số đứng đúng thứ tự lá của cách chia chẵn lẻ.

C++

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]);
}

Bước 2: gộp khối bằng phép bướm. len là độ dài khối đang gộp. w = 3^{(p-1)/len} là căn bậc len của đơn vị theo mô-đun $p$ , vì 3 là căn nguyên thủy của $998244353$ . Mỗi cặp cho u + v·wn ở nửa trên và u − v·wn ở nửa dưới.

C++

for (int len = 2; len <= n; len <<= 1) {
    ll w = power(3, (MOD - 1) / len);
    if (inv) w = power(w, MOD - 2);
    for (int i = 0; i < n; i += len) {
        ll wn = 1;
        for (int j = 0; j < len / 2; j++) {
            ll u = a[i + j], v = a[i + j + len / 2] * wn % MOD;
            a[i + j] = (u + v) % MOD;
            a[i + j + len / 2] = (u - v + MOD) % MOD;
            wn = wn * w % MOD;
        }
    }
}

Bước 3: biến đổi ngược. Dùng căn nghịch đảo w^{-1} (dòng if (inv) ở trên) rồi nhân mọi phần tử với $n^{-1}$ .

C++

if (inv) {
    ll ni = power(n, MOD - 2);
    for (int i = 0; i < n; i++) a[i] = a[i] * ni % MOD;
}

Bước 4: nhân. Chỉ in $n + m - 1$ hệ số đầu; phần đệm phía sau bằng 0.

C++

ntt(a, 0), ntt(b, 0);
for (int i = 0; i < sz; i++) a[i] = a[i] * b[i] % MOD;
ntt(a, 1);

Code đầy đủ

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

const ll MOD = 998244353;

ll power(ll a, ll b) {
    ll r = 1;
    a %= MOD;
    while (b) {
        if (b & 1) r = r * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return r;
}

void ntt(vector<ll> &a, bool inv) {
    int n = a.size();
    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]);
    }
    for (int len = 2; len <= n; len <<= 1) {
        ll w = power(3, (MOD - 1) / len);
        if (inv) w = power(w, MOD - 2);
        for (int i = 0; i < n; i += len) {
            ll wn = 1;
            for (int j = 0; j < len / 2; j++) {
                ll u = a[i + j], v = a[i + j + len / 2] * wn % MOD;
                a[i + j] = (u + v) % MOD;
                a[i + j + len / 2] = (u - v + MOD) % MOD;
                wn = wn * w % MOD;
            }
        }
    }
    if (inv) {
        ll ni = power(n, MOD - 2);
        for (int i = 0; i < n; i++) a[i] = a[i] * ni % MOD;
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, m;
    cin >> n >> m;
    int sz = 1;
    while (sz < n + m - 1) sz <<= 1;
    vector<ll> a(sz), b(sz);
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < m; i++) cin >> b[i];
    ntt(a, 0), ntt(b, 0);
    for (int i = 0; i < sz; i++) a[i] = a[i] * b[i] % MOD;
    ntt(a, 1);
    for (int i = 0; i < n + m - 1; i++) cout << a[i] << ' ';
    cout << '\n';
}

Input2 2
12 32
33 76

Output396 1968 2432

Ba lần biến đổi, mỗi lần $O(sz \log sz)$ . Vòng trong của NTT chạy hàng chục triệu lần, nên bớt phép chia dư ở đó có ích:

Nhân hai đa thức 524288 hệ số bằng NTT, hai cách cài.

Tính trước bảng căn đơn vị của từng tầng, và thay % MOD sau phép cộng, trừ bằng một phép so sánh, cho kết quả nhanh hơn bản trong bài khoảng 1,4 lần. Quy tắc: % chỉ cần ở phép nhân, cộng trừ thì dùng if.

FFT số thực

Khi cần kết quả chính xác lớn hơn mô-đun (như số cặp, tới $4 \cdot 10^{10}$ ), NTT theo một mô-đun không đủ. FFT trên số phức complex<double> cho kết quả gần đúng; làm tròn llround(x.real()) là đúng khi sai số dưới $0.5$ . Sai số tăng theo độ lớn hệ số và $\log n$ ; kinh nghiệm an toàn là tích các hệ số lớn nhất nhân độ dài không quá khoảng $10^{14}$ đến $10^{15}$ . Vượt mức đó thì tách hệ số làm hai nửa bit, hoặc dùng NTT theo hai, ba mô-đun rồi ghép bằng định lý thặng dư Trung Hoa.

Hỏi nhanh

Đếm cặp (táo, chuối) theo tổng trọng lượng với $2 \cdot 10^5$ quả mỗi loại. Vì sao không dùng NTT mô-đun $998244353$ trực tiếp?

Ví dụGhép cặp theo tổng khối lượng

Đề. $n$ táo và $m$ chuối, trọng lượng trong $[1, k]$ , $k, n, m \le 2 \cdot 10^5$ . Với mỗi tổng $w = 2..2k$ , đếm số cặp táo, chuối có tổng trọng lượng $w$ .

Lời giải. Đặt $A(x) = \sum a_w x^w$ với $a_w$ là số táo nặng $w$ , tương tự $B$ cho chuối. Số cặp có tổng $w$ là hệ số $x^w$ của $A \cdot B$ . Một hệ số có thể tới $n \cdot m = 4 \cdot 10^{10}$ , lớn hơn mô-đun của NTT, nên dùng FFT số phức rồi làm tròn. Hệ số đầu vào nhỏ (không quá $2 \cdot 10^5$ ) nên sai số còn xa $0{,}5$ .

Bước 1: FFT số phức. Cùng khung với ntt của ví dụ trước. Căn đơn vị là số phức $e^{2\pi i / len}$ ; biến đổi ngược đổi dấu góc rồi chia cho $n$ . wn *= w tích lũy sai số qua len / 2 bước; với độ dài $2^{19}$ và hệ số cỡ này vẫn đủ.

C++

double ang = 2 * PI / len * (inv ? -1 : 1);
cd w(cos(ang), sin(ang));

Bước 2: đếm và đọc kết quả. a[x] += 1 đếm số quả theo trọng lượng; sz đủ chứa bậc $2k$ của tích. Kết quả lấy llround(a[w].real()), phần ảo chỉ là sai số.

C++

fft(a, 0), fft(b, 0);
for (int i = 0; i < sz; i++) a[i] *= b[i];
fft(a, 1);
for (int w = 2; w <= 2 * k; w++) cout << llround(a[w].real()) << ' ';

Code đầy đủ

#include <bits/stdc++.h>
using namespace std;
#define ll long long
using cd = complex<double>;

const double PI = acos(-1);

void fft(vector<cd> &a, bool inv) {
    int n = a.size();
    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]);
    }
    for (int len = 2; len <= n; len <<= 1) {
        double ang = 2 * PI / len * (inv ? -1 : 1);
        cd w(cos(ang), sin(ang));
        for (int i = 0; i < n; i += len) {
            cd wn(1);
            for (int j = 0; j < len / 2; j++) {
                cd u = a[i + j], v = a[i + j + len / 2] * wn;
                a[i + j] = u + v;
                a[i + j + len / 2] = u - v;
                wn *= w;
            }
        }
    }
    if (inv)
        for (int i = 0; i < n; i++) a[i] /= n;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int k, n, m;
    cin >> k >> n >> m;
    int sz = 1;
    while (sz < 2 * k + 1) sz <<= 1;
    vector<cd> a(sz), b(sz);
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        a[x] += 1;
    }
    for (int i = 0; i < m; i++) {
        int x;
        cin >> x;
        b[x] += 1;
    }
    fft(a, 0), fft(b, 0);
    for (int i = 0; i < sz; i++) a[i] *= b[i];
    fft(a, 1);
    for (int w = 2; w <= 2 * k; w++) cout << llround(a[w].real()) << ' ';
    cout << '\n';
}

Input6 4 5
2 5 4 5
4 1 2 5 5

Output0 1 1 1 4 4 1 4 4 0 0

Độ phức tạp: $O(k \log k)$ .

Tương quan

Tích chập ghép các cặp có tổng chỉ số cố định. Muốn ghép theo hiệu chỉ số (khoảng cách, độ dịch), đảo một dãy: đặt $b'_j = b_{m - 1 - j}$ thì

\sum_j a_{j + s} b_j = \sum_j a_{j + s} b'_{m - 1 - j} = (a * b')_{s + m - 1}.

Vậy một tích chập cho kết quả của mọi độ dịch $s$ cùng lúc. So khớp xâu nhị phân: số vị trí khác nhau khi đặt $T$ tại $p$ là $\sum (s_{p+j} - t_j)^2 = \sum s_{p+j} + \sum t_j - 2 \sum s_{p+j} t_j$ , hai tổng đầu lấy từ tổng tiền tố, tổng cuối là một tương quan. Với bảng chữ nhiều ký tự thì tương quan riêng từng ký tự, hoặc mã hóa thành số và dùng $\sum (a - b)^2$ .

Ví dụKhoảng cách giữa các bit một

Đề. Xâu nhị phân dài $n \le 2 \cdot 10^5$ . Với mỗi $k = 1..n-1$ , đếm cặp $i$ với $s_i = s_{i+k} = 1$ .

Lời giải. Số cặp với khoảng cách $k$ là $\sum_i s_i s_{i+k}$ , một tương quan của $s$ với chính nó. Đặt $b_j = s_{n-1-j}$ (dãy đảo) thì $\sum_i s_{i+k} s_i = \sum_i s_{i+k}\, b_{n-1-i} = (s * b)_{n-1+k}$ . Một tích chập cho đáp án của mọi $k$ cùng lúc. Số cặp không quá $n$ , nhỏ hơn mô-đun, nên NTT cho đúng giá trị thật. power, ntt giống hệt ví dụ đầu bài.

Bước 1: dãy và dãy đảo. Một dòng đặt cả hai; sz phải chứa $2n - 1$ hệ số của tích.

C++

for (int i = 0; i < n; i++) a[i] = b[n - 1 - i] = s[i] - '0';

Bước 2: đọc kết quả. Đáp án của $k$ ở chỉ số $n - 1 + k$ ; chỉ số nhỏ hơn $n - 1$ ứng với độ dịch âm, chỉ số $n - 1$ là $k = 0$ , đều không cần in.

C++

for (int k = 1; k < n; k++) cout << a[n - 1 + k] << ' ';

Code đầy đủ

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

const ll MOD = 998244353;

ll power(ll a, ll b) {
    ll r = 1;
    a %= MOD;
    while (b) {
        if (b & 1) r = r * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return r;
}

void ntt(vector<ll> &a, bool inv) {
    int n = a.size();
    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]);
    }
    for (int len = 2; len <= n; len <<= 1) {
        ll w = power(3, (MOD - 1) / len);
        if (inv) w = power(w, MOD - 2);
        for (int i = 0; i < n; i += len) {
            ll wn = 1;
            for (int j = 0; j < len / 2; j++) {
                ll u = a[i + j], v = a[i + j + len / 2] * wn % MOD;
                a[i + j] = (u + v) % MOD;
                a[i + j + len / 2] = (u - v + MOD) % MOD;
                wn = wn * w % MOD;
            }
        }
    }
    if (inv) {
        ll ni = power(n, MOD - 2);
        for (int i = 0; i < n; i++) a[i] = a[i] * ni % MOD;
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    string s;
    cin >> s;
    int n = s.size(), sz = 1;
    while (sz < 2 * n - 1) sz <<= 1;
    vector<ll> a(sz), b(sz);
    for (int i = 0; i < n; i++) a[i] = b[n - 1 - i] = s[i] - '0';
    ntt(a, 0), ntt(b, 0);
    for (int i = 0; i < sz; i++) a[i] = a[i] * b[i] % MOD;
    ntt(a, 1);
    for (int k = 1; k < n; k++) cout << a[n - 1 + k] << ' ';
    cout << '\n';
}

Input101

Output0 1

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

Ví dụĐoạn nhị phân gần nhất

Đề. Hai xâu nhị phân $|T| \le |S| \le 10^6$ . Đổi ít ký tự nhất của $T$ để nó trùng một đoạn liên tiếp của $S$ .

Lời giải. Đặt $T$ bắt đầu ở vị trí $p$ của $S$ . Với bit, $s \ne t$ đúng khi $(s - t)^2 = 1$ , và $(s - t)^2 = s + t - 2st$ . Cộng lại trên cửa sổ, số chỗ khác là

\sum_j s_{p+j} + \sum_j t_j - 2 \sum_j s_{p+j} t_j.

Tổng đầu lấy từ tổng tiền tố, tổng thứ hai là hằng số, tổng cuối là tương quan, tính cho mọi $p$ bằng một tích chập với $T$ đảo như ví dụ trước. Độ dài tới $2 \cdot 10^6$ nên NTT dài $2^{21}$ .

Bước 1: chuẩn bị. pre là tổng tiền tố số bit 1 của $S$ ; ones là số bit 1 của $T$ ; b là $T$ đảo.

C++

for (int i = 0; i < n; i++) a[i] = s[i] - '0', pre[i + 1] = pre[i] + a[i];
for (int j = 0; j < m; j++) b[m - 1 - j] = t[j] - '0', ones += t[j] - '0';

Bước 2: thử mọi vị trí. Sau tích chập, a[p + m - 1] là $\sum_j s_{p+j} t_j$ . Tương quan không quá $m \le 10^6$ , nhỏ hơn mô-đun, nên giá trị sau NTT là giá trị thật.

C++

for (int p = 0; p + m <= n; p++) best = min(best, pre[p + m] - pre[p] + ones - 2 * a[p + m - 1]);

Code đầy đủ

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

const ll MOD = 998244353;

ll power(ll a, ll b) {
    ll r = 1;
    a %= MOD;
    while (b) {
        if (b & 1) r = r * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return r;
}

void ntt(vector<ll> &a, bool inv) {
    int n = a.size();
    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]);
    }
    for (int len = 2; len <= n; len <<= 1) {
        ll w = power(3, (MOD - 1) / len);
        if (inv) w = power(w, MOD - 2);
        for (int i = 0; i < n; i += len) {
            ll wn = 1;
            for (int j = 0; j < len / 2; j++) {
                ll u = a[i + j], v = a[i + j + len / 2] * wn % MOD;
                a[i + j] = (u + v) % MOD;
                a[i + j + len / 2] = (u - v + MOD) % MOD;
                wn = wn * w % MOD;
            }
        }
    }
    if (inv) {
        ll ni = power(n, MOD - 2);
        for (int i = 0; i < n; i++) a[i] = a[i] * ni % MOD;
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    string s, t;
    cin >> s >> t;
    int n = s.size(), m = t.size(), sz = 1;
    while (sz < n + m - 1) sz <<= 1;
    vector<ll> a(sz), b(sz);
    vector<int> pre(n + 1);
    int ones = 0;
    for (int i = 0; i < n; i++) a[i] = s[i] - '0', pre[i + 1] = pre[i] + a[i];
    for (int j = 0; j < m; j++) b[m - 1 - j] = t[j] - '0', ones += t[j] - '0';
    ntt(a, 0), ntt(b, 0);
    for (int i = 0; i < sz; i++) a[i] = a[i] * b[i] % MOD;
    ntt(a, 1);
    ll best = LLONG_MAX;
    for (int p = 0; p + m <= n; p++) best = min(best, pre[p + m] - pre[p] + ones - 2 * a[p + m - 1]);
    cout << best << '\n';
}

Input001111
11

Output0

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

Lũy thừa đa thức

Ở dạng giá trị, nhân đa thức là nhân từng điểm, nên lũy thừa cũng là lũy thừa từng điểm: một lần NTT thuận với độ dài đủ chứa bậc của kết quả, lũy thừa nhanh mỗi điểm, một lần NTT ngược, tổng $O(n \log n)$ thay vì $O(n \log n \log k)$ của bình phương liên tiếp. Đếm số cách chọn $k$ phần tử có tổng $s$ từ một tập giá trị cho phép là hệ số $x^s$ của $P(x)^k$ với $P$ là đa thức chỉ báo của tập.

Hỏi nhanh

Chữ số cho phép là $\{0, 1\}$ , vé dài 4. Có bao nhiêu vé cân bằng (tổng hai chữ số đầu bằng tổng hai chữ số cuối)?

Ví dụVé cân bằng

Đề. Vé có $n \le 10^5$ chữ số ( $n$ chẵn) lấy từ một tập $k \le 10$ chữ số. Đếm số vé có tổng nửa đầu bằng tổng nửa sau, theo mô-đun $998244353$ .

Lời giải. $P(x) = \sum_{d} x^d$ trên các chữ số cho phép. Số cách viết nửa vé có tổng $s$ là hệ số $Q_s$ của $Q = P^{n/2}$ . Nửa đầu và nửa sau chọn độc lập, nên số vé cân bằng là $\sum_s Q_s^2$ .

Bước 1: độ dài đủ chứa $Q$ . $Q$ có bậc tới $9n/2$ , nên sz là lũy thừa của 2 không nhỏ hơn $9 \cdot n/2 + 1$ , tức tới $2^{19}$ . Bậc của $Q$ không vượt độ dài nên không có hệ số nào bị cộng vòng.

Bước 2: lũy thừa từng điểm. Ở dạng giá trị, nhân đa thức là nhân từng điểm, nên lũy thừa đa thức là lũy thừa từng điểm. Chỉ hai lần biến đổi thay vì $\log n$ lần bình phương đa thức.

C++

ntt(p, 0);
for (int i = 0; i < sz; i++) p[i] = power(p[i], half);
ntt(p, 1);

Bước 3: cộng bình phương. ans cộng $Q_s^2$ trên mọi $s$ , kể cả phần đệm (bằng 0).

C++

for (int i = 0; i < sz; i++) ans = (ans + p[i] * p[i]) % MOD;

Code đầy đủ

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

const ll MOD = 998244353;

ll power(ll a, ll b) {
    ll r = 1;
    a %= MOD;
    while (b) {
        if (b & 1) r = r * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return r;
}

void ntt(vector<ll> &a, bool inv) {
    int n = a.size();
    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]);
    }
    for (int len = 2; len <= n; len <<= 1) {
        ll w = power(3, (MOD - 1) / len);
        if (inv) w = power(w, MOD - 2);
        for (int i = 0; i < n; i += len) {
            ll wn = 1;
            for (int j = 0; j < len / 2; j++) {
                ll u = a[i + j], v = a[i + j + len / 2] * wn % MOD;
                a[i + j] = (u + v) % MOD;
                a[i + j + len / 2] = (u - v + MOD) % MOD;
                wn = wn * w % MOD;
            }
        }
    }
    if (inv) {
        ll ni = power(n, MOD - 2);
        for (int i = 0; i < n; i++) a[i] = a[i] * ni % MOD;
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, k;
    cin >> n >> k;
    int half = n / 2, sz = 1;
    while (sz < 9 * half + 1) sz <<= 1;
    vector<ll> p(sz);
    for (int i = 0; i < k; i++) {
        int d;
        cin >> d;
        p[d] = 1;
    }
    ntt(p, 0);
    for (int i = 0; i < sz; i++) p[i] = power(p[i], half);
    ntt(p, 1);
    ll ans = 0;
    for (int i = 0; i < sz; i++) ans = (ans + p[i] * p[i]) % MOD;
    cout << ans << '\n';
}

Input4 2
0 1

Output6

Độ phức tạp: $O(sz \log sz)$ với $sz \le 2^{19}$ .

Khi đi thi

Tổng dạng $\sum_{i + j = k}$ hay $\sum_{i - j = s}$ trên mọi $k$ , $s$ : tích chập, đảo một dãy cho hiệu. Đếm cặp theo tổng giá trị: đa thức đếm theo giá trị.
Mô-đun $998244353$ : NTT. Kết quả thật lớn, không lấy dư: FFT số thực khi đủ chính xác, ngược lại tách hệ số hay dùng nhiều mô-đun.
Độ dài biến đổi là lũy thừa của 2 không nhỏ hơn bậc kết quả cộng 1; lũy thừa đa thức thì độ dài phải chứa cả bậc của lũy thừa.

Tóm tắt

FFT, NTT: đổi sang giá trị tại căn đơn vị, nhân từng điểm, đổi ngược; $O(n \log n)$ .
$998244353 = 119 \cdot 2^{23} + 1$ với căn nguyên thủy 3 cho NTT tới độ dài $2^{23}$ .
Tương quan theo độ dịch là tích chập với một dãy đảo ngược.
Lũy thừa đa thức: lũy thừa từng điểm ở dạng giá trị.

Bài tập

Nhân hai đa thức nguyêncanuc80k6801

LQDOJ

Tương quan hai tín hiệucanuc80k6803

LQDOJ

Hai cú đánh tới lỗcanuc80k6805

LQDOJ

Thống kê đoạn theo ngưỡngcanuc80k6807

LQDOJ

Các tổng của đúng k móncanuc80k6808

LQDOJ

Nghịch thế A-B theo khoảng cáchcanuc80k6810

LQDOJ

Khớp DNA trong vùng lân cậncanuc80k6811

LQDOJ

Hợp nhất sáu ký tựcanuc80k6812

LQDOJ

Các độ dịch an toàncanuc80k6813

LQDOJ

Tổng OR lớn nhất sau phép xoaycanuc80k6815

LQDOJ

Tích chập theo mô-đun 1e9+7canuc80k6816

LQDOJ

Nhân số nguyên thập phân dàicanuc80k6817

LQDOJ

Chọn số kiếm theo màucanuc80k6819

LQDOJ

Nghịch đảo chuỗi lũy thừacanuc80k6821

LQDOJ

Khớp mẫu có ký tự đại diệncanuc80k6845

LQDOJ

Đọc thêm

Biến đổi Fourier nhanhVNOI Wiki
Fast Fourier transformcp-algorithms
Introduction to Fast Fourier TransformUSACO Guide
快速傅里叶变换OI Wiki