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

• View this file on GitHub
• Last update: 2024-01-12 04:16:01+09:00
• Include: #include "FPS/compexp.hpp"

Depends on

• Sum of Rationals (FPS/sumofRationals.hpp)

Code

#pragma once
#include "FPS/sumofRationals.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 3 "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