test/fps_bostan_mori.test.cpp

• View this file on GitHub
• Last update: 2021-10-25 13:43:12+09:00
• Problem: https://judge.yosupo.jp/problem/kth_term_of_linearly_recurrent_sequence

Depends on

• atcoder/convolution.hpp
• 形式的冪級数 (atcoder/fps.hpp)
• atcoder/internal_bit.hpp
• atcoder/internal_math.hpp
• atcoder/internal_type_traits.hpp
• atcoder/modint.hpp

Code

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

#include <atcoder/fps>
#include <iostream>

using namespace atcoder;
using namespace std;

int main() {
    int d; long long k;
    cin >> d >> k;
    fps a(d), c(d+1);
    for (int i = 0; i < d; i++) { int t; cin >> t; a[i] = t; }
    for (int i = 0; i < d; i++) { int t; cin >> t; c[i+1] = -t; }
    c[0] = 1;
    a = convolution(a, c);
    a.resize(d);

    cout << bostan_mori(a, c, k).val() << endl;
}

#line 1 "test/fps_bostan_mori.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/kth_term_of_linearly_recurrent_sequence"

#include <atcoder/fps>
#include <iostream>

using namespace atcoder;
using namespace std;

int main() {
    int d; long long k;
    cin >> d >> k;
    fps a(d), c(d+1);
    for (int i = 0; i < d; i++) { int t; cin >> t; a[i] = t; }
    for (int i = 0; i < d; i++) { int t; cin >> t; c[i+1] = -t; }
    c[0] = 1;
    a = convolution(a, c);
    a.resize(d);

    cout << bostan_mori(a, c, k).val() << endl;
}

Back to top page