A Simple Math Problem Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 6592 Accepted Submission(s): 4047
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
代码：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mem(x,y) memset(x,y,sizeof(x))
const ll maxn = 11;
ll m,mod;
struct matrix
{
int n;
ll d[maxn][maxn];
void init(int n)
{
this -> n = n;
mem(d,0);
}
matrix operator *(matrix & b)
{
matrix ans;
ans.init(n);
for (int i = 0;i < n;i ++)
for (int j = 0;j < n;j ++)
{
for (int k = 0;k < n;k ++)
ans.d[i][j]=(ans.d[i][j]+d[i][k]*b.d[k][j])%mod;
}
return ans;
}
};
matrix quick(matrix a,ll b)
{
matrix res;
res.init(a.n);
for (int i = 0;i < res.n;i ++)
res.d[i][i] = 1;
while (b)
{
if (b & 1) res = res * a;
a = a * a;
b >>= 1;
}
return res;
}
int main()
{
while (~scanf("%lld %lld",&m,&mod))
{
matrix x;
x.init(10);
for (int i = 0;i < 10;i ++)
scanf("%lld",&x.d[9 - i][9]);
if (m < 10)
{
printf("%lld\n",m % mod);
continue;
}
for (int i = 0;i < 9;i ++)
x.d[i + 1][i] = 1;
x = quick(x,m - 9);
matrix ans;
ans.init(10);
for (int i = 0;i < 10;i ++) ans.d[0][i] = i;
ans = ans * x;
printf("%lld\n",ans.d[0][9]);
}
return 0;
}
