Enumerate $\sum_{k=0}^{N-1} k^i$
(FPS/prefixsumofpowers.hpp)

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

Code

#pragma once

template<typename T>vector<T> PrefixSumOfPowers(ll n,int k){ // 0<=i<=k,sum_n=0^{N-1} n^i
    Poly<T> num(k+1),den(k+1);
    num[0]=n,den[0]=1;
    rep(i,0,k)num[i+1]=num[i]*n;
    rep(i,0,k+1){
        num[i]*=Fact<T>(i+1,1);
        den[i]=Fact<T>(i+1,1);
    }
    num*=den.inv();
    num.resize(k+1);
    rep(i,0,k+1)num[i]*=Fact<T>(i);
    return num;
}

/**
 * @brief Enumerate $\sum_{k=0}^{N-1} k^i$
*/

#line 2 "FPS/prefixsumofpowers.hpp"

template<typename T>vector<T> PrefixSumOfPowers(ll n,int k){ // 0<=i<=k,sum_n=0^{N-1} n^i
    Poly<T> num(k+1),den(k+1);
    num[0]=n,den[0]=1;
    rep(i,0,k)num[i+1]=num[i]*n;
    rep(i,0,k+1){
        num[i]*=Fact<T>(i+1,1);
        den[i]=Fact<T>(i+1,1);
    }
    num*=den.inv();
    num.resize(k+1);
    rep(i,0,k+1)num[i]*=Fact<T>(i);
    return num;
}

/**
 * @brief Enumerate $\sum_{k=0}^{N-1} k^i$
*/

Back to top page