首页 > 代码库 > 九度OJ题目1443:Tr A (JAVA)
九度OJ题目1443:Tr A (JAVA)
- 题目描述:
-
A为一个方阵,则Tr A表示A的迹(就是主对角线上各项的和),现要求Tr(A^k)%9973。
- 输入:
-
数据的第一行是一个T,表示有T组数据。
每组数据的第一行有n(2 <= n <= 10)和k(2 <= k < 10^9)两个数据。接下来有n行,每行有n个数据,每个数据的范围是[0,9],表示方阵A的内容。
- 输出:
-
对应每组数据,输出Tr(A^k)%9973。
- 样例输入:
-
2 2 2 1 0 0 1 3 99999999 1 2 3 4 5 6 7 8 9
- 样例输出:
-
2 2686
1 package a; 2 import java.util.*; 3 public class Main{ 4 public static void main(String[] args) { 5 Scanner cin = new Scanner(System.in); 6 while(cin.hasNext()){ 7 int t=cin.nextInt(); 8 while(t!=0){ 9 int count=0; 10 int n=cin.nextInt(); 11 int k=cin.nextInt(); 12 int a[][]=new int[n][n]; 13 int c[][]=new int[n][n]; 14 for(int i=0;i<n;i++){ 15 for(int j=0;j<n;j++){ 16 a[i][j]=cin.nextInt(); 17 if(i==j) 18 c[i][j]=1;//初始化成单位数组。 19 else c[i][j]=0; 20 } 21 } 22 while(k!=0) {//二分法求幂。 23 if(k%2 == 1) 24 c = fuc(a, c); 25 k /= 2; 26 a = fuc(a, a); 27 } 28 for(int i=0;i<n;i++){ 29 count+=c[i][i]; 30 count%=9973; 31 32 } 33 System.out.println(count); 34 t--; 35 } 36 } 37 cin.close(); 38 } 39 public static int[][] fuc(int a[][],int b[][]){ 40 int c[][]=new int[a.length][a.length]; 41 for(int i=0;i<c.length;i++){//矩阵乘法三个循环。 42 for(int j=0;j<c.length;j++){ 43 for(int k=0;k<c.length;k++){ 44 c[i][j]+=a[i][k]*b[k][j];//别忘了这个加号。 45 c[i][j]%=9973; 46 } 47 } 48 } 49 return c; 50 } 51 }
九度OJ题目1443:Tr A (JAVA)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。