$\Pi_{k=0}^{m-1} f(r^kx)$
(FPS/prodoffrkx.hpp)

• View this file on GitHub
• Last update: 2023-01-17 01:58:11+09:00
• Include: #include "FPS/prodoffrkx.hpp"

Verified with

• Verify/YUKI_2097.test.cpp

Code

#pragma once

template<typename T>Poly<T> ProdOf_f_rk_x(Poly<T>& f,T r,int m){ // f(x)f(rx)...f(r^{m-1}x)
    assert(f[0]==1);
    T pwr=1,rm=T(r).pow(m),pwrm=1;
    auto g=f.log();
    rep(i,1,g.size()){
        pwr*=r;
        pwrm*=rm;
        if(pwr==1)g[i]*=m;
        else g[i]*=(pwrm-1)/(pwr-1);
    }
    return g.exp();
}

/**
 * @brief $\Pi_{k=0}^{m-1} f(r^kx)$
*/

#line 2 "FPS/prodoffrkx.hpp"

template<typename T>Poly<T> ProdOf_f_rk_x(Poly<T>& f,T r,int m){ // f(x)f(rx)...f(r^{m-1}x)
    assert(f[0]==1);
    T pwr=1,rm=T(r).pow(m),pwrm=1;
    auto g=f.log();
    rep(i,1,g.size()){
        pwr*=r;
        pwrm*=rm;
        if(pwr==1)g[i]*=m;
        else g[i]*=(pwrm-1)/(pwr-1);
    }
    return g.exp();
}

/**
 * @brief $\Pi_{k=0}^{m-1} f(r^kx)$
*/

Back to top page