test/fps/product_sequence.test.cpp

• View this file on GitHub
• Last update: 2024-06-19 18:48:40+09:00
• Problem: https://judge.yosupo.jp/problem/product_of_polynomial_sequence

Depends on

• fps/FPS_Product_Sequence.hpp

Code

#define PROBLEM "https://judge.yosupo.jp/problem/product_of_polynomial_sequence"

#include "../../fps/FPS_Product_Sequence.hpp"

#include <vector>
#include <iostream>


int main(){
    int N;
    std::cin >> N;
    std::vector<std::vector<atcoder::modint998244353>> f(N);
    for (int i = 0; i < N; i++){
        int d;
        std::cin >> d;
        f[i].resize(d + 1);
        for (int j = 0; j <= d; j++){
            int a;
            std::cin >> a;
            f[i][j] = a;
        }
    }
    auto ans = po167::FPS_Product_Sequence(f);
    for (int i = 0; i < (int)ans.size(); i++){
        if (i) std::cout << " ";
        std::cout << ans[i].val();
    }
    std::cout << "\n";
}

#line 1 "test/fps/product_sequence.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/product_of_polynomial_sequence"

#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());
}
}
#line 4 "test/fps/product_sequence.test.cpp"

#line 6 "test/fps/product_sequence.test.cpp"
#include <iostream>


int main(){
    int N;
    std::cin >> N;
    std::vector<std::vector<atcoder::modint998244353>> f(N);
    for (int i = 0; i < N; i++){
        int d;
        std::cin >> d;
        f[i].resize(d + 1);
        for (int j = 0; j <= d; j++){
            int a;
            std::cin >> a;
            f[i][j] = a;
        }
    }
    auto ans = po167::FPS_Product_Sequence(f);
    for (int i = 0; i < (int)ans.size(); i++){
        if (i) std::cout << " ";
        std::cout << ans[i].val();
    }
    std::cout << "\n";
}

Back to top page