fps/FPS_integral.hpp

• View this file on GitHub
• Last update: 2024-06-19 00:51:37+09:00
• Include: #include "fps/FPS_integral.hpp"

Required by

• fps/FPS_exp.hpp
• fps/FPS_inverse.hpp
• fps/FPS_log.hpp
• fps/FPS_pow.hpp
• fps/FPS_sum_of_power.hpp

Verified with

• test/fps/comp_inverse.test.cpp
• test/fps/exp.test.cpp
• test/fps/pow.test.cpp
• test/fps/sum_of_power.test.cpp

Code

#pragma once
#include <vector>

namespace po167{
template <class T>
std::vector<T> FPS_integral(std::vector<T> f){
    if (f.empty()) return f;
    std::vector<T> num_inv((int)f.size() + 1);
    num_inv[0] = 1;
    num_inv[1] = 1;
    auto m = T::mod();
    for (int i = 2; i <= (int)f.size(); i++){
        num_inv[i] = (0 - num_inv[m % i]) * (T)(m / i);
    }
    f.reserve((int)f.size() + 1);
    f.push_back(0);
    for (int i = (int)f.size() - 1; i > 0; i--){
        f[i] = f[i - 1] * num_inv[i];
    }
    f[0] = 0;
    return f;
}
}

#line 2 "fps/FPS_integral.hpp"
#include <vector>

namespace po167{
template <class T>
std::vector<T> FPS_integral(std::vector<T> f){
    if (f.empty()) return f;
    std::vector<T> num_inv((int)f.size() + 1);
    num_inv[0] = 1;
    num_inv[1] = 1;
    auto m = T::mod();
    for (int i = 2; i <= (int)f.size(); i++){
        num_inv[i] = (0 - num_inv[m % i]) * (T)(m / i);
    }
    f.reserve((int)f.size() + 1);
    f.push_back(0);
    for (int i = (int)f.size() - 1; i > 0; i--){
        f[i] = f[i - 1] * num_inv[i];
    }
    f[0] = 0;
    return f;
}
}

Back to top page