HDU 1575 Tr A（简单矩阵快速幂）

思路：简单矩阵快速幂，算完 A^k 后再求一遍主对角线上的和取个模

/*************************************************************************

    > File Name: hdu1575.cpp

    > Author:    WArobot

    > Blog:      http://www.cnblogs.com/WArobot/

    > Created Time: 2017年05月02日 星期二 20时42分37秒

 ************************************************************************/

#include<bits/stdc++.h>

using namespace std;

#define MOD 9973

#define mod(x) ((x)%MOD)

#define ll long long

const int maxn = 10;

struct mat{

	int m[maxn][maxn];

}unit;

int n;

ll  k;

mat operator * (mat a,mat b){

	mat ret;

	ll x;

	for(int i=0;i<n;i++){

		for(int j=0;j<n;j++){

			x = 0;

			for(int k=0;k<n;k++)

				x += mod( (ll)a.m[i][k]*b.m[k][j] );

			ret.m[i][j] = x;

		}

	}

	return ret;

}

void init_unit(){

	for(int i=0;i<maxn;i++)	unit.m[i][i] = 1;

	return;

}

mat pow_mat(mat a,ll x){

	mat ret = unit;

	while(x){

		if(x&1)		ret = ret*a;

		a = a*a;

		x >>= 1;

	}

	return ret;

}

int main(){

	int t;

	init_unit();

	scanf("%d",&t);

	while(t--){

		scanf("%d%lld",&n,&k);

		mat a;

		for(int i=0;i<n;i++)

			for(int j=0;j<n;j++)

				scanf("%d",&a.m[i][j]);

		mat ans = pow_mat(a,k);

		ll sum = 0;

		for(int i=0;i<n;i++)

			sum += ans.m[i][i];

		printf("%lld\n",sum%MOD);

	}

	return 0;

}

巴特西

HDU 1575 Tr A（简单矩阵快速幂）

最新文章

热门文章

巴特西

HDU 1575 Tr A（ 简单矩阵快速幂 ）

最新文章

热门文章

HDU 1575 Tr A（简单矩阵快速幂）