HDU——1575 Tr A（矩阵快速幂）

A为一个方阵，则Tr A表示A的迹（就是主对角线上各项的和），现要求Tr(A^k)%9973。

Input

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

Output

对应每组数据，输出Tr(A^k)%9973。

Sample Input

Sample Output

2
2686

题意：求(A^k)%9973 的主对角线之和。

题解：矩阵快速幂的简单应用，可以说是模板题了。详细请见代码。

C++：

#include <iostream>
#include <cstring>
using namespace std;
const int mod=9973;
int n,m;
struct hh{
	int a[15][15];
}x;//开一个二维数组表示矩阵
hh mul(hh x,hh y,int c){// 矩阵乘法公式
	hh w;
	memset(w.a,0,sizeof(w.a));
	for (int i = 0; i < n;i++){
		for (int j = 0; j < n;j++){
			for (int k = 0; k < n;k++){
				w.a[i][j]=(w.a[i][j]%c+(((x.a[i][k]%c)*(y.a[k][j]%c))%c)%c)%c;
			}// 模运算公式(a+b)%c=(a%c+b%c)%c和(a*b)%c=((a%c)*(b%c))%c,当然这里可以简化写。
		}// 简化写的形式为 w.a[i][j]=(w.a[i][j]%c+(x.a[i][k]%c)*(y.a[k][j]%c)%c)%c;
	}
	return w;
}
hh j_quick(hh a,int b,int c){// 矩阵快速幂（注意与普通快速幂的区别与联系）
	hh ans;
	memset(ans.a,0,sizeof(ans.a));
	for (int i = 0; i < n;i++){// 相当于普通快速幂的  ans=1；
		ans.a[i][i]=1;
	}
	while(b!=0){
		if(b&1)  ans=mul(ans,a,c);// 相当于普通快速幂的 ans=(ans*a)%c;
		b>>=1;
		a=mul(a,a,c);// 相当于普通快速幂的 a=(a*a)%c;
	}
	return ans;
}
int main(){
	int t;
	cin >> t;
	while(t--){
		cin >> n >> m;
		for (int i = 0; i < n;i++){//输入矩阵
			for (int j = 0; j < n;j++){
				cin >> x.a[i][j];
			}
		}
		hh z=j_quick(x,m,mod);
		int sum=0;
		for (int i = 0; i < n;i++){//计算对角线之和  
			sum=(sum%mod+z.a[i][i]%mod)%mod;// 模运算公式 (a+b)%c=(a%c+b%c)%c
		}
		cout << sum << endl;
	}
	return 0;
}

java：解释同上

import java.util.*;
public class Main {
	static Scanner cin = new Scanner(System.in);
	static int n,k;
	static class hh{
		long [][] ma = new long [n+2][n+2];
		public hh() {
			for (int i = 0; i < n;i++) {
				for (int j = 0; j < n;j++) {
					ma[i][j]=0;
				}
			}
		}
	}
	static hh mul(hh a, hh b,long x) {
		hh c = new hh();
		for (int i = 0; i < n;i++) {
			for (int j = 0; j < n;j++) {
				for (int k = 0;k < n;k++) {
					c.ma[i][j]=(c.ma[i][j]+a.ma[i][k]*b.ma[k][j]%x)%x;
				}
			}
		}
		return c;
	}
	static hh quick(hh a,long w,long c) {
		hh tmp = new hh();
		for (int i = 0; i < n;i++) tmp.ma[i][i]=1;
		while(w!=0) {
			if(w%2==1) tmp=mul(tmp,a,c);
			w/=2;
			a=mul(a,a,c);
		}
		return tmp;
	}
	public static void main(String[] args){
		long t;
		t=cin.nextLong();
		while(t-->0) {
			n = cin.nextInt();
			k = cin.nextInt();
			hh a = new hh();
			hh b = new hh();
			for (int i = 0; i < n;i++) {
				for (int j = 0; j < n;j++) {
					a.ma[i][j]=cin.nextLong();
				}
			}
			b=quick(a,k,9973);
			long sum=0;
			for (int i = 0; i < n;i++) {
				sum=(sum%9973+b.ma[i][i]%9973)%9973;
			}
			System.out.println(sum%9973);
		}
	}
}