LC_kth_term_of_linearly_recurrent_sequence.test.cpp

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

#include "Template/template.hpp"
#include "Utility/fastio.hpp"
#include "Math/modint.hpp"
#include "Convolution/ntt.hpp"
#include "FPS/fps.hpp"
#include "FPS/nthterm.hpp"

using Fp = fp<998244353>;
NTT<Fp> ntt;
template <> void Poly<Fp>::NTT(bool inv) {
    ntt.ntt(*this, inv);
}

int main() {
    int d;
    ll k;
    cin >> d >> k;
    Poly<Fp> a(d), c(d + 1);
    rep(i, 0, d) cin >> a[i];
    c[0] = 1;
    rep(i, 1, d + 1) {
        cin >> c[i];
        c[i] = -c[i];
    }
    a *= c;
    a.resize(d);
    Fp res = nth<Fp>(a, c, k);
    cout << res << '\n';
    return 0;
}