hdu1757-- A Simple Math Problem（矩陣快速冪優化）
A Simple Math Problem
Time Limit:1000MS
Memory Limit:32768KB
64bit IO Format:%I64d
& %I64u
Submit Status
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
<喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+PC9wPgo8cHJlIGNsYXNzPQ=="brush:java;">#include
#include
#include
using namespace std ;
#define LL __int64
struct node{
LL a[12][12] ;
int n ;
};
node mul(node p,node q,LL m)
{
int i , j , k ;
node s ;
s.n = p.n ;
for(i = 0 ; i < p.n ; i++)
for(j = 0 ; j < p.n ; j++)
{
s.a[i][j] = 0 ;
for(k = 0 ; k < p.n ; k++)
s.a[i][j] = (s.a[i][j] + p.a[i][k]*q.a[k][j]) % m ;
}
return s ;
}
node pow(node p,LL k,LL m)
{
if( k == 1 )
return p ;
node s = pow(p,k/2,m) ;
s = mul(s,s,m) ;
if( k%2 )
{
s = mul(s,p,m) ;
}
return s ;
}
int main()
{
LL k , m , ans ;
int i , j ;
node p , s ;
while( scanf("%I64d %I64d", &k, &m) != EOF )
{
if(k < 10)
{
printf("%I64d\n", k) ;
continue ;
}
ans = 0 ;
p.n = 10 ;
for(i = 0 ; i < 10 ; i++)
{
for(j = 0 ; j < 10 ; j++)
p.a[i][j] = 0 ;
p.a[i][i+1] = 1 ;
}
for(i = 0 ; i < 10 ; i++)
scanf("%I64d", &p.a[i][0]) ;
s = pow(p,k-9,m) ;
for(i = 0 ; i < 10 ; i++)
ans = ( ans + (9-i)*s.a[i][0] ) % m ;
printf("%I64d\n", ans) ;
}
return 0 ;
}
