Skip to main content

library_checker/linear_algebra/
pow_of_matrix.rs

1use competitive::prelude::*;
2use competitive::{
3    algebra::AddMulOperation,
4    math::{MIntMatrix, Matrix},
5    num::mint_basic::MInt998244353 as M,
6};
7
8#[verify::library_checker("pow_of_matrix")]
9pub fn pow_of_matrix(reader: impl Read, writer: impl Write) {
10    prepare_io!(reader, writer);
11    sc!(n, k, a: [[M; n]; n]);
12    let a = Matrix::<AddMulOperation<_>>::from_vec(a);
13    let b = a.pow_frobenius(k);
14    pp!(@it2d b.data);
15}
16
17#[verify::library_checker("pow_of_matrix")]
18pub fn pow_of_matrix_strassen(reader: impl Read, writer: impl Write) {
19    prepare_io!(reader, writer);
20    sc!(n, k, a: [[M; n]; n]);
21    let a = Matrix::<AddMulOperation<_>>::from_vec(a);
22    let b = a.pow_strassen(k);
23    pp!(@it2d b.data);
24}