A Simple Math Problem
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1838 Accepted Submission(s): 1053
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
Author
linle
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std; const int N= ; struct node
{
__int64 mat[N][N];
}hxl;
int A[],k,m; void make_first(node *cur)
{
int i,j;
for(i=;i<=;i++)
for(j=;j<=;j++)
if(i==j)
cur->mat[i][j]=;
else cur->mat[i][j]=;
} struct node cheng(node cur,node now)
{
node ww;
int i,j,k;
memset(ww.mat,,sizeof(ww.mat));
for(i=;i<=;i++)
for(k=;k<=;k++)
if(cur.mat[i][k])
{
for(j=;j<=;j++)
if(now.mat[k][j])
{
ww.mat[i][j]+=cur.mat[i][k]*now.mat[k][j];
if(ww.mat[i][j]>=m)
ww.mat[i][j]%=m;
}
}
return ww;
} void power_sum2(int n)
{
__int64 sum=;
int i;
node cur,now=hxl;
make_first(&cur);
while(n)
{
if(n&)
{
cur=cheng(cur,now);
}
n=n>>;
now=cheng(now,now);
}
for(i=;i<=;i++)
sum= (sum+(-i)*cur.mat[][i])%m;
printf("%I64d\n",sum); } void make_ini()
{
int i,j;
if(k<=)
{
printf("%d\n",k);
return;
}
memset(hxl.mat,,sizeof(hxl.mat));
for(i=;i<=;i++)
hxl.mat[][i]=A[i]; for(i=;i<=;i++)// 初始化
for(j=;j<=;j++)
if(i-j==)
hxl.mat[i][j]=; power_sum2(k-);
} int main()
{
int i;
while(scanf("%d%d",&k,&m)>)
{
for(i=;i<=;i++)
scanf("%d",&A[i]);
make_ini();
// cs();
}
return ;
}
Source
Recommend
lcy