往届 ACM 队训练题 (参考)

1022. 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

提示

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

不限期开放

题目列表