A Simple Math Problem(HDOJ 1757)
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
My Code
就是我上一篇文章那题的强化版,只是不需要你算递推式了,直接告诉你而已,构造矩阵很容易,递推式的系数放在矩阵的第一行,之后一行依次一个就好了,用这个系数矩阵的k-9次乘初始的矩阵就行了,动手模拟一下,就理解了。
#include
#include
using namespace std;
int mod;
struct Matrix
{
int M[15][15];
};
Matrix mul(Matrix m1, Matrix m2, int n)
{
Matrix m3;
memset(m3.M, 0, sizeof(m3.M));
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
{
for (int k = 0; k < n; k++)
m3.M[i][j] += (m1.M[i][k] * m2.M[k][j]) % mod;
m3.M[i][j] %= mod;
}
return m3;
}
Matrix pow(Matrix m, int k, int n)
{
Matrix ans;
memset(ans.M, 0, sizeof(ans.M));
for (int i = 0; i < n; i++)
ans.M[i][i] = 1;
while (k)
{
if (k & 1)
ans = mul(ans, m, n);
m = mul(m, m, n);
k >>= 1;
}
return ans;
}
int main()
{
int n, k;
Matrix m;
Matrix ans;
for (int i = 0; i < 10; i++) //这里是初始的F(0)~F(9)
ans.M[i][0] = 9 - i;
while (cin >> n >> mod)
{
memset(m.M, 0, sizeof(m.M));
for (int i = 0; i < 10; i++) //构造矩阵,用矩阵快速幂求递推式
{
cin >> m.M[0][i];
m.M[i + 1][i] = 1;
}
if (n < 10)
cout << ans.M[9 - n][0] % mod << endl; //这边也要记得mod
else
cout << mul(pow(m, n - 9, 10), ans, 10).M[0][0] << endl;
}
return 0;
}