首页 > 代码库 > HDU 1575
HDU 1575
Tr A
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4604 Accepted Submission(s): 3461
Problem Description
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的内容。
每组数据的第一行有n(2 <= n <= 10)和k(2 <= k < 10^9)两个数据。接下来有n行,每行有n个数据,每个数据的范围是[0,9],表示方阵A的内容。
Output
对应每组数据,输出Tr(A^k)%9973。
Sample Input
2
2 2
1 0
0 1
3 99999999
1 2 3
4 5 6
7 8 9
Sample Output
2
2686
一个简单的矩阵快速幂,刚学 拿来练模版(网上随便找了个,可惜没找到结构体的那个)
#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<algorithm> #include<string.h> #include<map> #include<set> #include<queue> #include<vector> #include<cstdlib> typedef long long ll; typedef unsigned long long LL; using namespace std; const int INF=0x3f3f3f3f; const int num=100; const int mod=9973; int N; struct Mat{ int a[num][num]; void init(){ memset(a,0,sizeof(a)); for(int i=0;i<num;i++) a[i][i]=1; } }; //矩阵加法 Mat add(Mat a,Mat b){ Mat ans; for(int i=0;i<N;i++) for(int j=0;j<N;j++){ ans.a[i][j]=a.a[i][j]+b.a[i][j]; ans.a[i][j]=ans.a[i][j]%mod; } return ans; } //矩阵乘法 Mat mul(Mat a,Mat b){ Mat ans; for(int i=0;i<N;i++){ for(int j=0;j<N;j++){ ans.a[i][j]=0; for(int k=0;k<N;k++){ ans.a[i][j]+=a.a[i][k]*b.a[k][j]; } ans.a[i][j]=ans.a[i][j]%mod; } } return ans; } //矩阵快速幂 Mat power(Mat a,int n){ Mat ans; ans.init(); while(n){ if(n&1){ ans=mul(ans,a); } n=n>>1; a=mul(a,a); } return ans; } //矩阵的幂和 Mat pow_sum(Mat a,int n){ int m; Mat ans,pre; if(n==1){ return a; } m=n/2; pre=pow_sum(a,m); ans=add(pre,mul(pre,power(a,m))); if(n&1) ans=add(ans,power(a,n)); return ans; } void output(Mat a){ for(int i=0;i<N;i++){ for(int j=0;j<N;j++){ if(j==0)printf("%d",a.a[i][j]); else printf(" %d",a.a[i][j]); } printf("\n"); } } int main(){ int tt; int k,n; scanf("%d",&tt); while(tt--){ int t=0; scanf("%d%d",&n,&k); Mat a; N=n; for(int i=0;i<N;i++){ for(int j=0;j<N;j++) scanf("%d",&a.a[i][j]); } Mat ans=power(a,k); //output(ans); for(int i=0;i<N;i++){ t=(t+ans.a[i][i])%mod; } printf("%d\n",t); } return 0; }
HDU 1575
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。