首页 > 代码库 > hdu 1757 A Simple Math Problem (乘法矩阵)

hdu 1757 A Simple Math Problem (乘法矩阵)

2024-07-07 13:27:22   233人阅读

A Simple Math Problem

Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2441    Accepted Submission(s): 1415


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.
 

 

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.
 

 

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
 

 

Author
linle
 

 

Source
2007省赛集训队练习赛（6）_linle专场
 

 

Recommend
lcy   |   We have carefully selected several similar problems for you:  1588 3117 2276 2256 2254 
 

 开始没什么思路，后来还是没思路..

然后看解题报告，发现时乘法矩阵，关键点还是在构造矩阵上。

参考：http://blog.sina.com.cn/s/blog_79b832820100wnu3.html

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|

 

 

设为矩阵 A * 矩阵B =矩阵C

我们要求的是 f(k),就是矩阵C的最后一个元素，故依据矩阵的结合律，可看到

C=A*(A*(.....*(A*B))) ,要有k个A即 C=A^k*B ，然后就可以二分求A^k，最后乘上B就可以求得矩阵C

 

 1 //0MS    232K    1214 B    C++    
 2 #include<stdio.h>
 3 #include<string.h>
 4 #define N 15
 5 struct matrix{
 6     int g[N][N];
 7 }ans,temp;
 8 int g[N];
 9 int m;
10 matrix mul(matrix a,matrix b)
11 {
12     matrix c;
13     for(int i=0;i<10;i++)
14         for(int j=0;j<10;j++){
15             c.g[i][j]=0;
16             for(int k=0;k<10;k++)
17                 c.g[i][j]+=a.g[i][k]*b.g[k][j];
18                 c.g[i][j]%=m;
19         }
20     return c;
21 }
22 void solve(int k)
23 {
24     while(k){
25         if(k&1) ans=mul(temp,ans);
26         temp=mul(temp,temp);
27         k/=2;
28     }
29     int sum=0;
30     /*
31     for(int i=0;i<10;i++)
32         for(int j=0;j<10;j++)
33             printf(j==9?"%d\n":"%d ",ans.g[i][j]);
34     */
35     for(int i=0;i<10;i++){
36         sum+=ans.g[9][i]*i;
37         sum%=m;
38     }
39     printf("%d\n",sum);
40 }
41 int main(void)
42 {
43     int k;
44     while(scanf("%d%d",&k,&m)!=EOF)
45     {
46         for(int i=0;i<10;i++)
47             for(int j=0;j<10;j++)  
48                 temp.g[i][j]=ans.g[i][j]=0;
49         for(int i=0;i<10;i++)
50             scanf("%d",&g[i]);
51         for(int i=0;i<10;i++){
52             if(i<9) temp.g[i][i+1]=1;
53             ans.g[i][i]=1;
54             temp.g[9][i]=g[9-i];
55         }
56         solve(k-9);
57     }
58     return 0;
59 }

 

 


联系
我们