1125. Tr A

单点时限: 2.0 sec

内存限制: 256 MB

前面我们已经做了 $A^B \bmod C$,这里提高一下。相信大家也会轻松解决的。

$A$ 为一个方阵,则 $Tr(A)$ 表示 $A$ 的迹(就是主对角线上各项的和),现要求 $Tr(A^k) \bmod 9973$。

输入格式

数据的第一行是一个 $T$,表示有 $T$ 组数据。

每组数据的第一行有 $n$ $(2 \le n \le 10)$ 和 $k$ $(2 \le k < 10^9)$ 两个数据。接下来有 $n$ 行,每行有 $n$ 个数据,每个数据的范围是 $[0,9]$,表示方阵 $A$ 的内容。

输出格式

对应每组数据,输出 $Tr(A^k) \bmod 9973$。

样例

Input
2
2 2
1 0
0 1
3 99999999
1 2 3
4 5 6
7 8 9
Output
2
2686

提示

此题目用到了二分的思想,但是还需要了解矩阵相乘。

87 人解决,151 人已尝试。

119 份提交通过,共有 268 份提交。

4.0 EMB 奖励。

创建: 13 年,4 月前.

修改: 2 年,7 月前.

最后提交: 3 周,2 天前.

来源: partychen

题目标签