library_checker/other/kth_term_of_linearly_recurrent_sequence.rs
1use competitive::prelude::*;
2use competitive::{
3 math::Fps998244353,
4 num::{One, montgomery::MInt998244353 as M},
5};
6
7#[verify::library_checker("kth_term_of_linearly_recurrent_sequence")]
8pub fn kth_term_of_linearly_recurrent_sequence(reader: impl Read, writer: impl Write) {
9 prepare_io!(reader, writer);
10 sc!(d, k, a: [M; d], c: [M; d]);
11 let q = Fps998244353::one() - (Fps998244353::from_vec(c) << 1);
12 pp!(q.kth_term_of_linearly_recurrence(a, k));
13}