HDU 1575 Tr A----行列乗算問題.
10676 ワード
Tr A
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1994 Accepted Submission(s): 1472
Problem Description
Aが1つの行列である場合、Tr AはAの跡(主対角線上の各項目の和)を表し、Tr(A^k)%9973が要求される.
Input
データの最初の行はTであり、Tグループのデータがあることを示す.各データ群の最初の行にはn(2<=n<=10)とk(2<=k<10^9)の2つのデータがある.次に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
Author
xhd
Source
HDU 2007-1 Programming Contest
他の知識を学ぶために、まずマトリックスを勉強して基礎を築きます.
この問題は、難しくないです.テンプレートの問題です.
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1994 Accepted Submission(s): 1472
Problem Description
Aが1つの行列である場合、Tr AはAの跡(主対角線上の各項目の和)を表し、Tr(A^k)%9973が要求される.
Input
データの最初の行はTであり、Tグループのデータがあることを示す.各データ群の最初の行にはn(2<=n<=10)とk(2<=k<10^9)の2つのデータがある.次に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
Author
xhd
Source
HDU 2007-1 Programming Contest
他の知識を学ぶために、まずマトリックスを勉強して基礎を築きます.
この問題は、難しくないです.テンプレートの問題です.
1 #include<iostream>
2 #include<cstdio>
3 #include<cstdlib>
4 #include<cstring>
5 using namespace std;
6
7
8 struct node
9 {
10 __int64 mat[12][12];
11 }hxl,tom;
12
13 void make_first(node *cur,int n)
14 {
15 int i,j;
16 for(i=1;i<=n;i++)
17 for(j=1;j<=n;j++)
18 if(i==j)
19 cur->mat[i][j]=1;
20 else cur->mat[i][j]=0;
21 }
22
23 struct node cheng(node cur,node now,int n)
24 {
25 node ww;
26 int i,j,k;
27 memset(ww.mat,0,sizeof(ww.mat));
28 for(i=1;i<=n;i++)
29 for(k=1;k<=n;k++)
30 if(cur.mat[i][k])
31 {
32 for(j=1;j<=n;j++)
33 if(now.mat[k][j])
34 {
35 ww.mat[i][j]+=cur.mat[i][k]*now.mat[k][j];
36 if(ww.mat[i][j]>=9973)
37 ww.mat[i][j]%=9973;
38 }
39 }
40 return ww;
41 }
42
43 __int64 power_sum2(int n,int k)
44 {
45 int i;
46 __int64 sum=0;
47 make_first(&tom,n);
48 while(k)
49 {
50 if(k&1)
51 {
52 tom=cheng(tom,hxl,n);
53 }
54 k=k>>1;
55 hxl=cheng(hxl,hxl,n);
56 }
57 for(i=1;i<=n;i++)
58 sum=(sum+tom.mat[i][i])%9973;
59 return sum;
60 }
61
62 int main()
63 {
64 int T,n,k,i,j;
65 __int64 sum;
66 while(scanf("%d",&T)>0)
67 {
68 while(T--)
69 {
70 scanf("%d%d",&n,&k);
71 for(i=1;i<=n;i++)
72 for(j=1;j<=n;j++)
73 scanf("%I64d",&hxl.mat[i][j]);
74 sum=power_sum2(n,k);
75 printf("%I64d
",sum);
76 }
77 }
78 return 0;
79 }