library_checker/math/
kth_term_of_linearly_recurrent_sequence.rs

1use competitive::prelude::*;
2#[doc(no_inline)]
3pub use competitive::{
4    math::Fps998244353,
5    num::{One, montgomery::MInt998244353},
6};
7
8#[verify::library_checker("kth_term_of_linearly_recurrent_sequence")]
9pub fn kth_term_of_linearly_recurrent_sequence(reader: impl Read, mut writer: impl Write) {
10    let s = read_all_unchecked(reader);
11    let mut scanner = Scanner::new(&s);
12    scan!(scanner, d, k, a: [MInt998244353; d], c: [MInt998244353; d]);
13    let q = Fps998244353::one() - (Fps998244353::from_vec(c) << 1);
14    iter_print!(writer, q.kth_term_of_linearly_recurrence(a, k));
15}