HDU 1757 A Simple Math Problem

原题传送门：http://acm.hdu.edu.cn/showproblem.php?pid=1757

A Simple Math Problem

Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2480    Accepted Submission(s): 1441

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

 

 

Author

 

linle

 

 

Source

 

2007省赛集训队练习赛（6）_linle专场

 

 

 

Recommend

 

lcy   |   We have carefully selected several similar problems for you:  1588 3117 2276 2256 2604

分析：这道题如果用打表或者递归肯定都是TLE的，那么我们可以用什么办法解决呢。。答案当然是矩阵快速幂。关键在于矩阵怎么构造了= =，这个矩阵也不难构造，就拿第一个例子来说，我们可以构造矩阵

1  1  1  1  1  1  1  1  1  1

1 

    1            0

         1

    0       。

                      。

                               1   0

只要学过矩阵乘法运算，估计都应该已经知道怎么回事了！

 

#include<cstdio>
#include<cstring>
int k,m,ans;
struct Matrix{
    int mat[10][10];
    Matrix operator *(const Matrix rhs) const {
        Matrix temp;
        for(int i=0;i<10;i++){
            for(int j=0;j<10;j++){
                temp.mat[i][j] = 0;
                for(int k=0;k<10;k++){
                    temp.mat[i][j] += (this->mat[i][k] * rhs.mat[k][j])%m;
                    temp.mat[i][j] %= m;
                }
            }
        }
        return temp;
    }
};

Matrix ret,mt;
int main(){
    while(~scanf("%d%d",&k,&m))
    {
        ans = 0;
        memset(ret.mat,0,sizeof(ret.mat));
        memset(mt.mat,0,sizeof(mt.mat));
        for(int i=0;i<10;i++)
            ret.mat[i][i] = 1;
        for(int i=0;i<10;i++)
            scanf("%d",&mt.mat[0][i]);
        for(int i=1;i<10;i++)
            mt.mat[i][i-1] = 1;
        k = k-9;
        while(k)
        {
            if(k&1) ret = ret * mt;
            k>>=1;
            mt = mt*mt;
        }
        for(int i=0;i<10;i++)
            ans = (ans + ret.mat[0][i]*(9-i))%m;
        printf("%d\n",ans);
    }

    return 0;
}