library

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

---

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

$f(\exp(x))$
(FPS/compexp.hpp)

• View this file on GitHub
• Last update: 2024-10-22 03:59:04+09:00
• Include: #include "FPS/compexp.hpp"

Depends on

• Sum of Rationals (FPS/sumofRationals.hpp)
• Combination (Math/comb.hpp)

Code

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

template <typename T> Poly<T> CompExp(Poly<T> &f, int m) {
    int n = f.size();
    vector<pair<Poly<T>, Poly<T>>> fs;
    rep(i, 0, n) {
        Poly<T> p({Fp(f[i])});
        Poly<T> q({Fp(1), Fp(-i)});
        fs.push_back({p, q});
    }
    auto [p, q] = SumOfRationals(fs);
    q.resize(m);
    p *= q.inv();
    p.resize(m);
    rep(i, 0, m) p[i] *= Fact<T>(i, 1);
    return p;
}

/**
 * @brief $f(\exp(x))$
 */

#line 2 "FPS/sumofRationals.hpp"

template<typename T>pair<Poly<T>,Poly<T>> SumOfRationals(vector<pair<Poly<T>,Poly<T>>>& fs){
    using Ratio=pair<Poly<T>,Poly<T>>;
    if(fs.empty())return {Poly<T>({T(1)}),Poly<T>({T(1)})};
    sort(ALL(fs),[&](Ratio& a,Ratio& b){return a.first.size()+a.second.size()<b.first.size()+b.second.size();});
    deque<Ratio> deq;
    for(auto& f:fs)deq.push_back(f);
    while(deq.size()>1){
        auto [f,g]=deq[0];
        auto [p,q]=deq[1];
        deq.push_back({f*q+g*p,g*q});
        deq.pop_front();
        deq.pop_front();
    }
    return deq[0];
}

/**
 * @brief Sum of Rationals
*/
#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/compexp.hpp"

template <typename T> Poly<T> CompExp(Poly<T> &f, int m) {
    int n = f.size();
    vector<pair<Poly<T>, Poly<T>>> fs;
    rep(i, 0, n) {
        Poly<T> p({Fp(f[i])});
        Poly<T> q({Fp(1), Fp(-i)});
        fs.push_back({p, q});
    }
    auto [p, q] = SumOfRationals(fs);
    q.resize(m);
    p *= q.inv();
    p.resize(m);
    rep(i, 0, m) p[i] *= Fact<T>(i, 1);
    return p;
}

/**
 * @brief $f(\exp(x))$
 */

Back to top page