fps/FPS_Product_Sequence.hpp

• View this file on GitHub
• Last update: 2024-06-19 18:48:40+09:00
• Include: #include "fps/FPS_Product_Sequence.hpp"

Required by

• fps/FPS_sum_of_power.hpp

Verified with

• test/fps/product_sequence.test.cpp
• test/fps/sum_of_power.test.cpp

Code

#pragma once
#include <vector>
#include <atcoder/convolution>

namespace po167{
template<class T>
std::vector<T> FPS_Product_Sequence(std::vector<std::vector<T>> f){
    if (f.empty()) return {1};
    auto op = [&](auto self,int l, int r) -> std::vector<T> {
        if (l + 1 == r) return f[l];
        int m = (l + r) / 2;
        return atcoder::convolution(self(self, l, m), self(self, m, r));
    };
    return op(op, 0, f.size());
}
}

#line 2 "fps/FPS_Product_Sequence.hpp"
#include <vector>
#include <atcoder/convolution>

namespace po167{
template<class T>
std::vector<T> FPS_Product_Sequence(std::vector<std::vector<T>> f){
    if (f.empty()) return {1};
    auto op = [&](auto self,int l, int r) -> std::vector<T> {
        if (l + 1 == r) return f[l];
        int m = (l + r) / 2;
        return atcoder::convolution(self(self, l, m), self(self, m, r));
    };
    return op(op, 0, f.size());
}
}

Back to top page