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;
}