library

This documentation is automatically generated by online-judge-tools/verification-helper

Project maintained by tko919 Hosted on GitHub Pages — Theme by mattgraham

:warning: Compositional Inverse
(FPS/compinv.hpp)

Depends on

Code

#pragma once
#include "FPS/powenum.hpp"
#include "Math/comb.hpp"

template <typename T> Poly<T> CompositionInv(Poly<T> &f) {
    assert(SZ(f) >= 2 and f[0] == 0 and f[1] != 0);
    const int n = f.deg();
    const T c = f[1];
    const T invc = c.inv();
    for (auto &x : f)
        x *= invc;
    Poly<T> g(n + 1);
    g[n] = 1;
    auto ret = Poly<Fp>{PowEnumerate(f, g, n)};
    rep(i, 1, n + 1) ret[i] *= T(n) * Inv<T>(i);
    reverse(ALL(ret));
    ret[0] = 1;
    ret = ret.log();
    const T invn = T(1) / -n;
    for (auto &x : ret)
        x *= invn;
    ret = (ret.exp()) << 1;
    ret.resize(n + 1);
    T buf = 1;
    for (auto &x : ret) {
        x *= buf;
        buf *= invc;
    }
    return ret;
}

/**
 * @brief Compositional Inverse
 */
#line 2 "FPS/powenum.hpp"

template <typename T>
vector<T> PowEnumerate(Poly<T> &f, Poly<T> &g,
                       int m) { // sum_j g_j [x^j] f^i (i=0..m)
    assert(f[0] == 0);
    int n = 1;
    while (n < SZ(f))
        n <<= 1;
    int k = 1;
    Poly<T> P(n * 2), Q(n * 2);
    f.resize(n);
    g.resize(n);
    reverse(ALL(g));
    rep(i, 0, n) P[i] = g[i];
    rep(i, 1, n) Q[i] = -f[i];

    while (n > 1) {
        auto R = Q;
        rep(i, 0, SZ(R)) if (i & 1) R[i] = -R[i];
        auto PR = P * R;
        auto QR = Q * R;
        PR.resize(4 * n * k);
        QR.resize(4 * n * k);
        rep(i, 0, n * k * 2) {
            PR[2 * n * k + i] += P[i];
            QR[2 * n * k + i] += Q[i] + R[i];
        }
        P.assign(n * 2 * k, 0);
        Q.assign(n * 2 * k, 0);
        rep(j, 0, k * 2) rep(i, 0, n / 2) {
            P[j * n + i] = PR[j * 2 * n + i * 2 + 1];
            Q[j * n + i] = QR[j * 2 * n + i * 2];
        }
        n >>= 1;
        k <<= 1;
    }
    vector<T> ret(k);
    rep(i, 0, k) ret[i] = P[i * 2];
    reverse(ALL(ret));
    ret.resize(m + 1);
    return ret;
}

/**
 * @brief Pow Enumerate
 */
#line 2 "Math/comb.hpp"

template <typename T> T Inv(ll n) {
    static int md;
    static vector<T> buf({0, 1});
    if (md != T::get_mod()) {
        md = T::get_mod();
        buf = vector<T>({0, 1});
    }
    assert(n > 0);
    n %= md;
    while (SZ(buf) <= n) {
        int k = SZ(buf), q = (md + k - 1) / k;
        buf.push_back(buf[k * q - md] * q);
    }
    return buf[n];
}

template <typename T> T Fact(ll n, bool inv = 0) {
    static int md;
    static vector<T> buf({1, 1}), ibuf({1, 1});
    if (md != T::get_mod()) {
        md = T::get_mod();
        buf = ibuf = vector<T>({1, 1});
    }
    assert(n >= 0 and n < md);
    while (SZ(buf) <= n) {
        buf.push_back(buf.back() * SZ(buf));
        ibuf.push_back(ibuf.back() * Inv<T>(SZ(ibuf)));
    }
    return inv ? ibuf[n] : buf[n];
}

template <typename T> T nPr(int n, int r, bool inv = 0) {
    if (n < 0 || n < r || r < 0)
        return 0;
    return Fact<T>(n, inv) * Fact<T>(n - r, inv ^ 1);
}
template <typename T> T nCr(int n, int r, bool inv = 0) {
    if (n < 0 || n < r || r < 0)
        return 0;
    return Fact<T>(n, inv) * Fact<T>(r, inv ^ 1) * Fact<T>(n - r, inv ^ 1);
}
// sum = n, r tuples
template <typename T> T nHr(int n, int r, bool inv = 0) {
    return nCr<T>(n + r - 1, r - 1, inv);
}
// sum = n, a nonzero tuples and b tuples
template <typename T> T choose(int n, int a, int b) {
    if (n == 0)
        return !a;
    return nCr<T>(n + b - 1, a + b - 1);
}

/**
 * @brief Combination
 */
#line 4 "FPS/compinv.hpp"

template <typename T> Poly<T> CompositionInv(Poly<T> &f) {
    assert(SZ(f) >= 2 and f[0] == 0 and f[1] != 0);
    const int n = f.deg();
    const T c = f[1];
    const T invc = c.inv();
    for (auto &x : f)
        x *= invc;
    Poly<T> g(n + 1);
    g[n] = 1;
    auto ret = Poly<Fp>{PowEnumerate(f, g, n)};
    rep(i, 1, n + 1) ret[i] *= T(n) * Inv<T>(i);
    reverse(ALL(ret));
    ret[0] = 1;
    ret = ret.log();
    const T invn = T(1) / -n;
    for (auto &x : ret)
        x *= invn;
    ret = (ret.exp()) << 1;
    ret.resize(n + 1);
    T buf = 1;
    for (auto &x : ret) {
        x *= buf;
        buf *= invc;
    }
    return ret;
}

/**
 * @brief Compositional Inverse
 */
Back to top page