首页 > 代码库 > HDU 1575 EASY

HDU 1575 EASY

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm> using namespace std; int n,M=9973;struct Matrax {    int m[15][15];}; Matrax a,per; void initial(){    int i,j;    for(i=0;i<n;i++){        for(j=0;j<n;j++){            scanf("%d",&a.m[i][j]);            a.m[i][j]%=M;            per.m[i][j]=(i==j);        }    }} Matrax multi(Matrax a,Matrax b){    Matrax c;    int k,i,j;    for(i=0;i<n;i++){        for(j=0;j<n;j++){            c.m[i][j]=0;            for(k=0;k<n;k++){                c.m[i][j]=(c.m[i][j]+a.m[i][k]*b.m[k][j])%M;            }            c.m[i][j]%=M;        }    }    return c;} Matrax Power(int k){    Matrax c,p,ans=per;    p=a;    while(k){        if(k&1){            ans=multi(ans,p);            k--;        }        else {            k/=2;            p=multi(p,p);        }    }    return ans;}int main(){	int t,k;	scanf("%d",&t);	while(t--){		scanf("%d%d",&n,&k);		initial();		Matrax ans=Power(k);		int ant=0;		for(int i=0;i<n;i++)		ant=(ant+ans.m[i][i])%M;		printf("%d\n",ant);	}	return 0;}

  

HDU 1575 EASY