首页 > 代码库 > HDU1757：A Simple Math Problem（矩阵快速幂）
HDU1757：A Simple Math Problem（矩阵快速幂）
http://acm.hdu.edu.cn/showproblem.php?pid=1757
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
题目解析：
前面已经写了一篇博客如何构造矩阵，这道题可以说就是上片博客的简单应用。
矩阵的乘法不满足交换律，但是却满足结合律，如：A*B*C=A*(B*C);
f(x) = a0 * f(x-1) + a1 * f(x-2) + a2 * f(x-3) + …… + a9 * f(x-10)
构造的矩阵是:
|0 1 0 ......... 0| |f0| |f1 |
|0 0 1 0 ...... 0| |f1| |f2 |
|...................1| * |..| = |...|
|a9 a8 .......a0| |f9| |f10|
然后根据矩阵的结合律，可以先把构造的矩阵的K次幂求出来。最后直接求第一个数。
代码：
#include <iostream>#include <string>#include <stdlib.h>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;struct ma{ int a[10][10];} init,res;int K;int mod,b[10],f[10];ma Mul(ma x,ma y){ ma tmp; for(int i=0; i<10; i++) for(int j=0; j<10; j++) { tmp.a[i][j]=0; for(int k=0; k<10; k++) tmp.a[i][j]=(tmp.a[i][j]+x.a[i][k]*y.a[k][j])%mod; } return tmp;}ma Pow(ma x,int K){ ma tmp; for(int i=0; i<10; i++) { for(int j=0; j<10; j++) tmp.a[i][j]=(i==j); } while(K!=0) { if(K&1) tmp=Mul(tmp,x); K>>=1; x=Mul(x,x); } return tmp;}int main(){ while(scanf("%d%d",&K,&mod)!=EOF) { for(int i=0; i<=9; i++) { scanf("%d",&init.a[9][9-i]); } if(K<=9) { printf("%d\n",K); continue; } for(int i=0; i<10; i++) f[i]=i; for(int i=0; i<=8; i++) { for(int j=0; j<=9; j++) init.a[i][j]=(i==j-1); } res=Pow(init,K); int ans=0; for(int j=0; j<10; j++) { ans=(ans+res.a[0][j]*j)%mod; } printf("%d\n",ans); } return 0;}
加深印象，写了两次。
#include <iostream>#include <string>#include <stdlib.h>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;struct ma{ int a[10][10];} init,res;int K;int mod,b[10],f[10];ma Mul(ma x,ma y){ ma tmp; for(int i=0; i<10; i++) for(int j=0; j<10; j++) { tmp.a[i][j]=0; for(int k=0; k<10; k++) tmp.a[i][j]=(tmp.a[i][j]+x.a[i][k]*y.a[k][j])%mod; } return tmp;}ma Pow(ma x,int K){ ma tmp; for(int i=0; i<10; i++) { for(int j=0; j<10; j++) tmp.a[i][j]=(i==j); } while(K!=0) { if(K&1) tmp=Mul(tmp,x); K>>=1; x=Mul(x,x); } return tmp;}int main(){ while(scanf("%d%d",&K,&mod)!=EOF) { for(int i=0; i<=9; i++) { scanf("%d",&init.a[9][9-i]); } if(K<=9) { printf("%d\n",K); continue; } for(int i=0; i<10; i++) f[i]=i; for(int i=0; i<=8; i++) { for(int j=0; j<=9; j++) init.a[i][j]=(i==j-1); } res=Pow(init,K-9); int ans=0; for(int j=0; j<10; j++) { ans=(ans+(res.a[9][j])*f[j])%mod; } printf("%d\n",ans); } return 0;}
HDU1757：A Simple Math Problem（矩阵快速幂）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。