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
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.
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.
开始没什么思路，后来还是没思路..
然后看解题报告，发现时乘法矩阵，关键点还是在构造矩阵上。
参考：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
//0MS 232K 1214 B C++
#include<stdio.h>
#include<string.h>
#define N 15
struct matrix{
int g[N][N];
}ans,temp;
int g[N];
int m;
matrix mul(matrix a,matrix b)
{
matrix c;
for(int i=;i<;i++)
for(int j=;j<;j++){
c.g[i][j]=;
for(int k=;k<;k++)
c.g[i][j]+=a.g[i][k]*b.g[k][j];
c.g[i][j]%=m;
}
return c;
}
void solve(int k)
{
while(k){
if(k&) ans=mul(temp,ans);
temp=mul(temp,temp);
k/=;
}
int sum=;
/*
for(int i=0;i<10;i++)
for(int j=0;j<10;j++)
printf(j==9?"%d\n":"%d ",ans.g[i][j]);
*/
for(int i=;i<;i++){
sum+=ans.g[][i]*i;
sum%=m;
}
printf("%d\n",sum);
}
int main(void)
{
int k;
while(scanf("%d%d",&k,&m)!=EOF)
{
for(int i=;i<;i++)
for(int j=;j<;j++)
temp.g[i][j]=ans.g[i][j]=;
for(int i=;i<;i++)
scanf("%d",&g[i]);
for(int i=;i<;i++){
if(i<) temp.g[i][i+]=;
ans.g[i][i]=;
temp.g[][i]=g[-i];
}
solve(k-);
}
return ;
}