HDU 1757 A Simple Math Problem 【矩阵经典7 构造矩阵递推式】

任意门：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): 6621    Accepted Submission(s): 4071

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

题意概括：

按照题目所给的递推式求解 f（N）；

解题思路：

根据递推式构造矩阵乘法；

然后矩阵快速幂解决矩阵乘法；

Ac code：

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#define LL long long
using namespace std;
const int N = ;
int Mod, K;

struct mat
{
    int m[][];
}base, tmp, ans;

mat muti(mat a, mat b)
{
    mat res;
    memset(res.m, , sizeof(res.m));
    for(int i = ; i <= N; i++)
    for(int j = ; j <= N; j++){
        if(a.m[i][j]){
            for(int k = ; k <= N; k++){
                res.m[i][k] = (res.m[i][k] + a.m[i][j] * b.m[j][k])%Mod;
            }
        }
    }
    return res;
}

mat qpow(mat a, int n)
{
    mat res;
    memset(res.m, , sizeof(res.m));
    for(int i = ; i <= N; i++) res.m[i][i] = 1LL;
    while(n){
        if(n&){
            res = muti(res, a);
        }
        a = muti(a, a);
        n>>=;
    }
    return res;
}

int main()
{

    while(~scanf("%d%d", &K, &Mod)){
        memset(base.m, , sizeof(base.m));
        for(int i = ; i < ; i++){
            base.m[i][] = i;
        }

        memset(tmp.m, , sizeof(tmp.m));
        for(int i = ; i <= ; i++){
            tmp.m[i][i+] = ;
        }
        for(int i = ; i >= ; i--){
            scanf("%d", &tmp.m[][i]);         //构造递推关系矩阵
            base.m[][] += ((LL)(i-)*tmp.m[][i])%Mod;
        }
        //see see
//            for(int i = 1; i <= 10; i++){
//                for(int j = 1; j <= 10; j++){
//                    printf("%d ", tmp.m[i][j]);
//                }
//                puts("");
//            }

        if(K <= ){
            printf("%d\n", base.m[K][]);
        }
        else{
            tmp = qpow(tmp, K-);
            ans = muti(tmp, base);
//            //see see
//            for(int i = 1; i <= 10; i++){
//                for(int j = 1; j <= 10; j++){
//                    printf("%d ", tmp.m[i][j]);
//                }
//                puts("");
//            }
            printf("%d\n", ans.m[][]%Mod);
        }
    }
    return ;
}