首页 > 代码库 > hdu------(1757)A Simple Math Problem(简单矩阵快速幂)
hdu------(1757)A Simple Math Problem(简单矩阵快速幂)
A Simple Math Problem
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2791 Accepted Submission(s): 1659
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 99991 1 1 1 1 1 1 1 1 120 5001 0 1 0 1 0 1 0 1 0
Sample Output
45104
Author
linle
Source
2007省赛集训队练习赛（6）_linle专场
代码：
1 //#define LOCAL 2 #include<cstdio> 3 #include<cstring> 4 #define LL __int64 5 using namespace std; 6 const int maxn=10; 7 LL k,m; 8 int aa[maxn],mat[maxn][maxn]; 9 int ans[maxn][maxn];10 11 void init()12 {13 for(int i=0;i<10;i++)14 {15 for(int j=0;j<10;j++)16 {17 if(i==0)18 mat[i][j]=aa[j];19 else20 if(i==j+1)mat[i][j]=1;21 else mat[i][j]=0;22 if(i==j)23 ans[i][j]=1;24 else ans[i][j]=0;25 }26 }27 }28 29 void Matrix(int a[][10],int b[][10])30 {31 32 int c[10][10];33 for(int i=0;i<10;i++)34 {35 for(int j=0;j<10;j++)36 {37 c[i][j]=0;38 for(int k=0;k<10;k++)39 {40 c[i][j]=(c[i][j]+a[i][k]*b[k][j])%m;41 }42 }43 }44 for(int i=0;i<10;i++)45 {46 for(int j=0;j<10;j++)47 {48 a[i][j]=c[i][j];49 }50 }51 }52 53 void pow(LL n)54 {55 while(n>0)56 {57 if(n&1) Matrix(ans,mat);58 n>>=1L;59 if(n==0)break;60 Matrix(mat,mat);61 }62 }63 64 int main()65 {66 #ifdef LOCAL67 freopen("test.in","r",stdin);68 #endif69 70 while(scanf("%I64d%I64d",&k,&m)!=EOF)71 {72 for(int i=0;i<10;i++)73 scanf("%d",aa+i);74 if(k<10) printf("%I64d\n",k%m);75 else76 {77 init();78 pow(k-9);79 int res=0;80 for(int i=0;i<10;i++)81 res=(res+(10-i-1)*ans[0][i])%m;82 printf("%d\n",res);83 }84 }85 return 0;86 }
hdu------(1757)A Simple Math Problem(简单矩阵快速幂)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。