Enumerate $\sum_k a_k^i$
(FPS/sumofpowers.hpp)

• View this file on GitHub
• Last update: 2023-01-17 03:46:43+09:00
• Include: #include "FPS/sumofpowers.hpp"

Depends on

• Product of Polynomials (FPS/prodofpolys.hpp)

Code

#pragma once
#include "FPS/prodofpolys.hpp"

template<typename T>vector<T> SumOfPowers(vector<T>& a,int m){//0<=i<=m,sum_k a_k^i
    int n=a.size();
    vector<Poly<T>> fs(n);
    rep(i,0,n)fs[i]=Poly<T>({T(1),T(-a[i])});
    auto ret=ProdOfPolys(fs);
    ret.resize(m+1);
    ret=ret.log();
    rep(i,0,m+1)ret[i]=-ret[i]*i;
    ret[0]=a.size();
    return ret;
}

/**
 * @brief Enumerate $\sum_k a_k^i$
*/

#line 2 "FPS/prodofpolys.hpp"

template<typename T>Poly<T> ProdOfPolys(vector<Poly<T>>& fs){
    if(fs.empty())return Poly<T>({T(1)});
    sort(ALL(fs),[&](Poly<T>& a,Poly<T>& b){return a.size()<b.size();});
    deque<Poly<T>> deq;
    for(auto& f:fs)deq.push_back(f);
    while(deq.size()>1){
        deq.push_back(deq[0]*deq[1]);
        deq.pop_front();
        deq.pop_front();
    }
    return deq[0];
}

/**
 * @brief Product of Polynomials
*/
#line 3 "FPS/sumofpowers.hpp"

template<typename T>vector<T> SumOfPowers(vector<T>& a,int m){//0<=i<=m,sum_k a_k^i
    int n=a.size();
    vector<Poly<T>> fs(n);
    rep(i,0,n)fs[i]=Poly<T>({T(1),T(-a[i])});
    auto ret=ProdOfPolys(fs);
    ret.resize(m+1);
    ret=ret.log();
    rep(i,0,m+1)ret[i]=-ret[i]*i;
    ret[0]=a.size();
    return ret;
}

/**
 * @brief Enumerate $\sum_k a_k^i$
*/

Back to top page