Prefix Sum of Polynomial
(FPS/prefixsumofpoly.hpp)

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

Depends on

• Famous Sequence (FPS/famous.hpp)

Code

#pragma once

#include "FPS/famous.hpp"

template<typename T>Poly<T> PrefixSum(Poly<T>& f){ // g(x)=sum_{y=0}^{x} f(y)
    if(f.empty())return {};
    int n=f.size();
    auto ber=Bernoulli<T>(n-1);
    if(n>=2)ber[1]=-ber[1];
    Poly<T> base(n);
    rep(i,0,n){
        ber[i]*=Fact<T>(i,1);
        if(i)base[i]=f[i]*Fact<T>(i);
    }
    reverse(ALL(ber));
    base*=ber;
    Poly<T> ret(n+1);
    ret[0]=f[0],ret[1]=f[0];
    rep(i,1,n+1){
        ret[i]+=base[i+n-2]*Fact<T>(i,1);
    }
    return ret;
}

/**
 * @brief Prefix Sum of Polynomial
*/

#line 2 "FPS/prefixsumofpoly.hpp"

#line 2 "FPS/famous.hpp"

template<typename T>vector<T> Bernoulli(int n){
    Poly<T> f(n+1);
    rep(i,0,n+1)f[i]=Fact<T>(i+1,1);
    f=f.inv();
    rep(i,0,n+1)f[i]*=Fact<T>(i);
    return f;
}

template<typename T>vector<T> Partition(int n){
    Poly<T> f(n+1);
    f[0]=1;
    rep(k,1,n+1){
        if(1LL*k*(3*k+1)/2<=n)f[1LL*k*(3*k+1)/2]+=(k&1?-1:1);
        if(1LL*k*(3*k-1)/2<=n)f[1LL*k*(3*k-1)/2]+=(k&1?-1:1);
    }
    return f.inv();
}

template<typename T>vector<T> StirlingNumber1st(int n){
    if(n==0)return Poly<T>({T(1)});
    Poly<T> f({T(0),T(1)});
    for(int LG=topbit(n)-1;LG>=0;LG--){
        int m=n>>LG;
        f*=f.shift(m>>1);
        if(m&1)f=(f<<1)+f*T(m-1);
    }
    rep(i,0,n+1)if((n-i)&1)f[i]=-f[i];
    return f;
}

template<typename T>vector<T> StirlingNumber2nd(int n){
    if(n==0)return Poly<T>({T(1)});
    Poly<T> f(n+1),g(n+1);
    rep(i,0,n+1){
        f[i]=Fp(i).pow(n)*Fact<T>(i,1);
        g[i]=Fact<T>(i,1);
        if(i&1)g[i]=-g[i];
    }
    f*=g;
    f.resize(n+1);
    return f;
}

template<typename T>vector<T> Bell(int n){
    Poly<T> f(n+1);
    if(n)f[1]=1;
    rep(i,2,n+1)f[i]=f[i-1]/i;
    f=f.exp();
    T fac=1;
    rep(i,2,n+1)fac*=i,f[i]*=fac;
    return f;
}

/**
 * @brief Famous Sequence
*/
#line 4 "FPS/prefixsumofpoly.hpp"

template<typename T>Poly<T> PrefixSum(Poly<T>& f){ // g(x)=sum_{y=0}^{x} f(y)
    if(f.empty())return {};
    int n=f.size();
    auto ber=Bernoulli<T>(n-1);
    if(n>=2)ber[1]=-ber[1];
    Poly<T> base(n);
    rep(i,0,n){
        ber[i]*=Fact<T>(i,1);
        if(i)base[i]=f[i]*Fact<T>(i);
    }
    reverse(ALL(ber));
    base*=ber;
    Poly<T> ret(n+1);
    ret[0]=f[0],ret[1]=f[0];
    rep(i,1,n+1){
        ret[i]+=base[i+n-2]*Fact<T>(i,1);
    }
    return ret;
}

/**
 * @brief Prefix Sum of Polynomial
*/

Back to top page