首页 > 代码库 > HDU 1575 && 1757 矩阵快速幂&&构造矩阵入门
HDU 1575 && 1757 矩阵快速幂&&构造矩阵入门
HDU 1575
Tr A
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2912 Accepted Submission(s): 2167
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
一个矩阵快速幂搞定。。
1 #include <cstdio> 2 #include <iostream> 3 #include <cstring> 4 #include <algorithm> 5 #include <vector> 6 #include <queue> 7 using namespace std; 8 #define MOD 9973 9 typedef __int64 LL;10 11 struct node{12 LL g[11][11];13 };14 15 int n, m;16 17 node cheng(node a,node b){18 node c;19 int i, j, k;20 21 memset(c.g,0,sizeof(c.g));22 for(i=0;i<n;i++){23 for(k=0;k<n;k++){24 if(!a.g[i][k]) continue;25 for(j=0;j<n;j++)26 c.g[i][j]=(c.g[i][j]+a.g[i][k]*b.g[k][j])%MOD;27 }28 }29 30 return c;31 }32 33 node pow(node a,int mm){34 node ans;35 int i, j;36 memset(ans.g,0,sizeof(ans.g));37 for(i=0;i<n;i++) ans.g[i][i]=1;38 while(mm){39 if(mm&1) ans=cheng(ans,a);40 a=cheng(a,a);41 mm>>=1;42 // cout<<mm<<endl;43 }44 45 return ans;46 }47 48 main()49 {50 int t, i, j, k;51 cin>>t;52 while(t--){53 node a;54 scanf("%d %d",&n,&m);55 for(i=0;i<n;i++){56 for(j=0;j<n;j++)57 scanf("%I64d",&a.g[i][j]);58 }59 60 a=pow(a,m);61 62 LL ans=0;63 for(i=0;i<n;i++){64 ans=(ans+a.g[i][i])%MOD;65 }66 printf("%I64d\n",ans);67 }68 }
HDU 1757
A Simple Math Problem
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2751 Accepted Submission(s): 1628
Problem Description
Lele now is thinking about a simple function f(x).
If x < 10 f(x) = x.
If x >= 10 f(x) = a0 * f(x-1) + a1 * f(x-2) + a2 * f(x-3) + …… + a9 * f(x-10);
And ai(0<=i<=9) can only be 0 or 1 .
Now, I will give a0 ~ a9 and two positive integers k and m ,and could you help Lele to caculate f(k)%m.
If x < 10 f(x) = x.
If x >= 10 f(x) = a0 * f(x-1) + a1 * f(x-2) + a2 * f(x-3) + …… + a9 * f(x-10);
And ai(0<=i<=9) can only be 0 or 1 .
Now, I will give a0 ~ a9 and two positive integers k and m ,and could you help Lele to caculate f(k)%m.
Input
The problem contains mutiple test cases.Please process to the end of file.
In each case, there will be two lines.
In the first line , there are two positive integers k and m. ( k<2*10^9 , m < 10^5 )
In the second line , there are ten integers represent a0 ~ a9.
In each case, there will be two lines.
In the first line , there are two positive integers k and m. ( k<2*10^9 , m < 10^5 )
In the second line , there are ten integers represent a0 ~ a9.
Output
For each case, output f(k) % m in one line.
Sample Input
10 9999
1 1 1 1 1 1 1 1 1 1
20 500
1 0 1 0 1 0 1 0 1 0
Sample Output
45
104
题目意思：
给出f[x]怎么得到，然后求f[k]%m。
思路：
这道题可以找通项公式来算，但是比较麻烦，而这道题很明显可以用矩阵相乘来算。
已知 当x<10 ,f[x]=x；
所以咱们可以由以下矩阵相乘算以后的项 ，如下：
| | |f[0]| |f[1]|
| | |f[1]| |f[2]|
| | |f[2]| |f[3]|
| | |f[3]| |f[4]|
| | * |f[4]| = |f[5]|
| | |f[5]| |f[6]|
| | |f[6]| |f[7]|
| | |f[7]| |f[8]|
| | |f[8]| |f[9]|
| | |f[9]| |f[10]|
（构造的矩阵a） （矩阵b） （矩阵c）
当x<10的时候直接输出即可，当x>10 ,a^(x-9)*b就可以得到f[x]了。
而a^(x-9)用矩阵快速幂可以快速算出，时间复杂度为O(logn)。
很容易得出构造的矩阵a为：
0,1,0,0,0,0,0,0,0,0
0,0,1,0,0,0,0,0,0,0
0,0,0,1,0,0,0,0,0,0
0,0,0,0,1,0,0,0,0,0
0,0,0,0,0,1,0,0,0,0
0,0,0,0,0,0,1,0,0,0
0,0,0,0,0,0,0,1,0,0
0,0,0,0,0,0,0,0,1,0
0,0,0,0,0,0,0,0,0,1
a9,a8,a7,a6,a5,a4,a3,a2,a1,a0
代码如下：
1 #include <cstdio> 2 #include <iostream> 3 #include <cstring> 4 #include <algorithm> 5 #include <vector> 6 #include <queue> 7 using namespace std; 8 9 typedef __int64 LL;10 int n;11 LL MOD;12 13 struct node{14 LL g[10][10];15 };16 int a[10];17 18 node init(){19 node c;20 int i;21 memset(c.g,0,sizeof(c.g));22 for(i=0;i<9;i++) c.g[i][i+1]=1;23 for(i=0;i<10;i++) c.g[9][i]=a[9-i];24 25 26 return c;27 }28 29 node cheng(node A,node B){30 node C;31 memset(C.g,0,sizeof(C.g));32 int i, j, k;33 for(i=0;i<10;i++){ //这里有个小技巧，把原本俩矩阵相乘的代码中j和k的位置换一下 ，很明显的提高了时间效率 34 for(k=0;k<10;k++){35 if(!A.g[i][k]) continue;36 for(j=0;j<10;j++)37 C.g[i][j]=(C.g[i][j]+A.g[i][k]*B.g[k][j])%MOD;38 }39 }40 return C;41 }42 43 node pow(node c,int mm){44 node A;45 int i;46 memset(A.g,0,sizeof(A.g));47 for(i=0;i<10;i++) A.g[i][i]=1;48 while(mm){49 if(mm&1) A=cheng(A,c);50 c=cheng(c,c);51 mm>>=1;52 }53 return A;54 }55 56 main()57 {58 int i, j, k;59 __int64 f[]={0,1,2,3,4,5,6,7,8,9};60 61 while(scanf("%d %I64d",&n,&MOD)==2){62 for(i=0;i<10;i++) scanf("%d",&a[i]);63 if(n<10) {printf("%I64d\n",f[n]);continue;}64 node c=init(); //构造矩阵 65 66 67 n=n-9;68 c=pow(c,n); //矩阵快速幂优化矩阵相乘 69 LL ans=0;70 for(i=0;i<10;i++)71 ans=(ans+c.g[9][i]*f[i])%MOD;72 printf("%I64d\n",ans);73 74 }75 }
HDU 1575 && 1757 矩阵快速幂&&构造矩阵入门
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。