FFT và NTT · FFT and NTT · Thuật toán Canuc80k

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. 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$ , nên hai nửa là hai bài cùng dạng kích thước một nửa. Phép “bướm”

Tích chập: ô (i, j) là a[i]·b[j], c[k] là tổng trên đường chéo i + j = k. Kéo k để xem từng đường chéo.

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$ .

NTT 8 điểm theo mod 17 (căn nguyên thủy 3). Mỗi tầng ghép từng cặp bằng u + v·w và u − v·w.

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;
using 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)$ .

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;
using 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

$O(k \log k)$ .

Tương quan: đảo một dãy

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;
using 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

$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;
using 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

$O(n \log n)$ .

Lũy thừa đa thức ở dạng giá trị

Ở 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;
using 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

$O(sz \log sz)$ với $sz \le 2^{19}$ .

Khi đi thi

Thấy 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ị.
Có 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 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

1

Nhân hai đa thức nguyêncanuc80k6801Hệ số nguyên có dấu, nhiều test: FFT số thực rồi làm tròn; đảm bảo độ lớn tích nằm trong vùng an toàn của double.

LQDOJ

2

Tương quan hai tín hiệucanuc80k6803Đảo mặt nạ rồi nhân với tín hiệu; giá trị tại độ dịch

s

nằm ở chỉ số

s + m - 1

.

LQDOJ

3

Hai cú đánh tới lỗcanuc80k6805Đa thức chỉ báo khoảng cách

D

; một hay hai cú tới được

q

khi hệ số

x^q

của

D + D^2

dương.

LQDOJ

4

Thống kê đoạn theo ngưỡngcanuc80k6807Gọi

c_i

là số phần tử nhỏ hơn

x

trong tiền tố; đếm cặp có

c_j - c_i = k

bằng tích chập phân bố

c

với bản đảo;

k = 0

tính riêng.

LQDOJ

5

Các tổng của đúng k móncanuc80k6808Lũy thừa

k

của đa thức chỉ báo giá, chỉ cần biết hệ số khác 0: NTT theo mô-đun rồi lũy thừa từng điểm.

LQDOJ

6

Nghịch thế A-B theo khoảng cáchcanuc80k6810Như khoảng cách giữa các bit một, nhưng tương quan giữa chỉ báo B và chỉ báo A.

LQDOJ

7

Khớp DNA trong vùng lân cậncanuc80k6811Với mỗi ký tự, đánh dấu vị trí của

S

có ký tự đó trong bán kính

k

; tương quan với chỉ báo ký tự trong

T

, cộng bốn ký tự, bằng

m

là khớp.

LQDOJ

8

Hợp nhất sáu ký tựcanuc80k6812Với mỗi cặp chữ

(a, b)

, tương quan chỉ báo

a

trong

S

và

b

trong

T

; tại mỗi vị trí nối các cặp có tương quan dương bằng DSU và đếm số lần hợp.

LQDOJ

9

Các độ dịch an toàncanuc80k6813Tương quan vị trí V với vị trí K cho các độ dịch xung đột;

d

an toàn khi mọi bội của

d

đều không xung đột.

LQDOJ

10

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

a \mathbin{\mathrm{OR}} b = a + b - (a \mathbin{\&} b)

; với mỗi bit, tương quan vòng chỉ báo bit trong

A

và

B

nhân đôi.

LQDOJ

11

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

10^9 + 7

không hợp NTT: ba NTT theo ba mô-đun rồi ghép bằng định lý thặng dư Trung Hoa, hoặc FFT tách hệ số thành hai nửa bit.

LQDOJ

12

Nhân số nguyên thập phân dàicanuc80k6817Chữ số là hệ số đa thức; nhân bằng NTT rồi xử lý nhớ từ hàng đơn vị lên, cẩn thận dấu.

LQDOJ

13

Chọn số kiếm theo màucanuc80k6819Tích các đa thức

1 + x + \dots + x^{c_i}

theo màu, nhân theo kiểu chia để trị để độ dài cân bằng; mô-đun 1009 cần FFT có tách hệ số.

LQDOJ

14

Nghịch đảo chuỗi lũy thừacanuc80k6821Nghịch đảo chuỗi lũy thừa bằng Newton:

g \leftarrow g(2 - fg)

, mỗi bước gấp đôi số hệ số đúng.

LQDOJ

15

Khớp mẫu có ký tự đại diệncanuc80k6845Mã hóa * là 0 và chữ là số dương; vị trí khớp khi

\sum (a - b)^2 ab = 0

, khai triển thành ba tích chập.

LQDOJ

Đọc thêm

Biến đổi Fourier nhanhVNOI WikiFFT, NTT và ứng dụng bằng tiếng Việt.
Fast Fourier transformcp-algorithmsCài đặt không đệ quy, NTT và các ứng dụng.
Introduction to Fast Fourier TransformUSACO GuideBài luyện tích chập.
快速傅里叶变换OI WikiChứng minh và tối ưu.