A Simple Math Problem
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2802 Accepted Submission(s): 1669
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.
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
/*
HDOJ 1757 矩阵快速幂
数论没怎么看 还是看别人的
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);
|f(10) | |a0 a1 a2 ...a8 a9| |f(9)|
| f(9) | | 1 0 0 ... 0 0| |f(8)|
| .....| = |.. ... ... ... ..| | .. | = A
| f(2) | | 0 0 0 ... 0 0| |f(1)|
| f(1) | | 0 0 0 ... 1 0| |f(0)|
然后就是上面那张图
(f(n),f(n-1),...,f(n-9))^(-1) = A^(n-9)*(f(9),f(8),...,f(0))^(-1)
*/
#include<iostream>
#include<stdio.h>
using namespace std;
#define N 10
struct node{
int map[N][N];
};
node matrix;
int k,m;
void init()
{
int i,j;
for(i=0;i<N;i++)
scanf("%d",&matrix.map[0][i]);//输入矩阵第一行的a0-a9
for(i=1;i<N;i++)
for(j=0;j<N;j++)
{
if(i==j+1)
matrix.map[i][j]=1;
else
matrix.map[i][j]=0;
}
}
//矩阵相乘
node multi(node a,node b)
{
node c;
int i,j,k;
for(i=0;i<N;i++)
for(j=0;j<N;j++)
{
c.map[i][j]=0;
for(k=0;k<N;k++)
c.map[i][j]+=a.map[i][k]*b.map[k][j];
c.map[i][j]%=m;
}
return c;
}
node matrixPow(int n)//计算A^n-9
{
node t;
if(n==1)
return matrix;
if(n&1)//n奇数
return multi(matrix,matrixPow(n-1));
else//n偶数 等于两个矩阵t 相乘
{
t=matrixPow(n/2);
return multi(t,t);
}
}
int main()
{
int ans,i;
//freopen("test.txt","r",stdin);
while(scanf("%d%d",&k,&m)!=EOF)
{
init();
if(k<10)
{
printf("%d\n",k%m);
continue;
}
node temp=matrixPow(k-9);//计算A^n-9
//最求得f(n)就是temp第一行和f[9],f[8],...,f[1],f[0]相乘，
//因为x<10 f(x)=x 就是x:N-i-1
ans=0;
for(i=0;i<N;i++)
{
ans+=temp.map[0][i]*(N-i-1);
ans%=m;
}
printf("%d\n",ans);
}
return 0;
}