P4721 【模板】分治 FFT

标签：limits int FFT rev len ++ long P4721 模板

最具经济性的写法：\(\mathcal O(n^2)\) 暴力拿下 \(80\) 分，遂跑路。

一题多解了，分两部分：分治 和 多项式求逆。

分治

考虑 cdq 分治，每次把 \(f_{l \dots mid}\) 和 \(g_{1 \dots n - 1}\) 卷起来，贡献直接加到 \(f_{mid + 1 \dots r}\) 里，要注意一下顺序，先递归左区间，再算当前区间，最后递归右区间，否则不能确保正确性。

时间复杂度 \(T(n) = 2T(\dfrac n2) + \mathcal O(n \log n) = \mathcal O(n \log n)\)。常数较大。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

constexpr int N = 1 << 17, MOD = 998244353;

int n, f[N], g[N], tf[N], tg[N];
int len, bits, rev[N], G[2][17];

ll qp(ll base, int e) {
    ll res = 1;
    while (e) {
        if (e & 1) res = res * base % MOD;
        base = base * base % MOD;
        e >>= 1;
    }
    return res;
}

void NTT(int *A, bool I = 0) {
    for (int i = 0; i < len; i++) if (i < rev[i]) swap(A[i], A[rev[i]]);
    for (int i = 1; i < len; i <<= 1) {
        ll wn = G[I][__builtin_ctz(i)];
        for (int j = 0; j < len; j += (i << 1)) {
            ll w = 1;
            for (int k = j; k < j + i; k++) {
                int t = w * A[k + i] % MOD;
                A[k + i] = (A[k] - t + MOD) % MOD, A[k] = (A[k] + t) % MOD;
                w = w * wn % MOD;
            }
        }
    }
    if (I) {
        ll invlen = qp(len, MOD - 2);
        for (int i = 0; i < len; i++) A[i] = A[i] * invlen % MOD;
    }
}

void cdq(int l, int r) {
    if (l == r) return;
    int mid = (l + r) >> 1; cdq(l, mid);
    len = 1, bits = -1; while (len <= r - l) len <<= 1, bits++;
    for (int i = 0; i < len; i++) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << bits);
    memset(tf, 0, len << 2), memcpy(tf, f + l, (mid - l + 1) << 2), memcpy(tg, g, (r - l + 1) << 2);
    NTT(tf), NTT(tg); for (int i = 0; i < len; i++) tf[i] = (ll)tf[i] * tg[i] % MOD; NTT(tf, 1);
    for (int i = mid + 1; i <= r; i++) f[i] = (f[i] + tf[i - l]) % MOD;
    cdq(mid + 1, r);
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(nullptr), cout.tie(nullptr);
    cin >> n;
    for (int i = 1; i < n; i++) cin >> g[i];
    for (int i = 0; i < 17; i++) G[0][i] = qp(3, (MOD - 1) / (1 << (i + 1))), G[1][i] = qp(G[0][i], MOD - 2);
    f[0] = 1, cdq(0, n - 1);
    for (int i = 0; i < n; i++) cout << f[i] << ' ';
    return 0;
}

多项式求逆

设 \(F(x) = \sum\limits_{i = 0}^\infin f_ix^i, G(x) = \sum\limits_{i = 0}^\infin g_ix^i, g_0 = 0\)。

有

\[F(x) * G(x) = \sum\limits_{i = 0}^{\infin}\sum\limits_{j = 0}^if_{i - j}g_jx^i = F(x) - f_0 = F(x) - 1 \]

故

\[F(x) * [1 - G(x)] \equiv 1 \pmod{x^n} \]

剩下的就是多项式乘法逆板子了。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

constexpr int N = 1 << 18, MOD = 998244353;

int n, f[N], g[N], fg[N];
int len, bits, rev[N], G[2][18];

ll qp(ll base, int e) {
    ll res = 1;
    while (e) {
        if (e & 1) res = res * base % MOD;
        base = base * base % MOD;
        e >>= 1;
    }
    return res;
}

void NTT(int *A, bool I = 0) {
    for (int i = 0; i < len; i++) if (i < rev[i]) swap(A[i], A[rev[i]]);
    for (int i = 1; i < len; i <<= 1) {
        ll wn = G[I][__builtin_ctz(i)];
        for (int j = 0; j < len; j += (i << 1)) {
            ll w = 1;
            for (int k = j; k < j + i; k++) {
                int t = w * A[k + i] % MOD;
                A[k + i] = (A[k] - t + MOD) % MOD, A[k] = (A[k] + t) % MOD;
                w = w * wn % MOD;
            }
        }
    }
    if (I) {
        ll invlen = qp(len, MOD - 2);
        for (int i = 0; i < len; i++) A[i] = A[i] * invlen % MOD;
    }
}

void solve(int e) {
    if (e == 1) return;
    solve((e + 1) >> 1);
    bits = -1, len = 1; while (len < (e << 1) - 1) len <<= 1, bits++;
    for (int i = 0; i < len; i++) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << bits);
    memcpy(fg, f, e << 2), fill(fg + e, fg + len, 0); NTT(fg), NTT(g);
    for (int i = 0; i < len; i++) fg[i] = (ll)fg[i] * g[i] % MOD;
    for (int i = 0; i < len; i++) g[i] = (ll)g[i] * (2 - fg[i] + MOD) % MOD;
    NTT(g, 1); fill(g + e, g + len, 0);
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(nullptr), cout.tie(nullptr);
    cin >> n; for (int i = 1; i < n; i++) cin >> f[i], f[i] = MOD - f[i];
    for (int i = 0; i < 18; i++) G[0][i] = qp(3, (MOD - 1) / (1 << (i + 1))), G[1][i] = qp(G[0][i], MOD - 2);
    g[0] = qp(f[0] = 1, MOD - 2); solve(n);
    for (int i = 0; i < n; i++) cout << g[i] << ' ';
    return 0;
}

标签：limits,int,FFT,rev,len,++,long,P4721,模板
From： https://www.cnblogs.com/chy12321/p/18011331