Skip to main content

library_checker/linear_algebra/
pow_of_matrix.rs

1use competitive::prelude::*;
2#[doc(no_inline)]
3pub use competitive::{algebra::AddMulOperation, math::Matrix, num::montgomery::MInt998244353};
4
5#[verify::library_checker("pow_of_matrix")]
6pub fn pow_of_matrix(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, n, k, a: [[MInt998244353; n]; n]);
10    let a = Matrix::<AddMulOperation<_>>::from_vec(a);
11    let b = a.pow(k);
12    iter_print!(writer, @it2d b.data);
13}
14
15#[verify::library_checker("pow_of_matrix")]
16pub fn pow_of_matrix_strassen(reader: impl Read, mut writer: impl Write) {
17    let s = read_all_unchecked(reader);
18    let mut scanner = Scanner::new(&s);
19    scan!(scanner, n, k, a: [[MInt998244353; n]; n]);
20    let a = Matrix::<AddMulOperation<_>>::from_vec(a);
21    let b = a.pow_strassen(k);
22    iter_print!(writer, @it2d b.data);
23}