#T30. 【模板】矩阵快速幂
【模板】矩阵快速幂
题目背景
矩阵快速幂
题目描述
给定 的矩阵 ,求 。
输入格式
第一行两个整数 接下来 行,每行 个整数,第 行的第 的数表示 。
输出格式
输出
共 行,每行 个数,第 行第 个数表示 ,每个元素对 取模。
2 1
1 1
1 1
1 1
1 1
提示
【数据范围】
对于 的数据:,,
矩阵快速幂
给定 n×n 的矩阵 A,求 Ak。
第一行两个整数 n,k 接下来 n 行,每行 n 个整数,第 i 行的第 j 的数表示 Ai,j。
输出 Ak
共 n 行,每行 n 个数,第 i 行第 j 个数表示 (Ak)i,j,每个元素对 109+7 取模。
2 1
1 1
1 1
1 1
1 1
【数据范围】
对于 100% 的数据:1≤n≤100,0≤k≤1012, ∣Ai,j∣≤1000