HDOJ 1757 A Simple Math Problem

题目意思：给定两个关系式，要求第k项模m的值，输入k 和 m

解题思路：

1 ：If x < 10 f(x) = x.
2 ：If x >= 10 f(x) = a0 * f(x-1) + a1 * f(x-2) + a2 * f(x-3) + …… + a9 * f(x-10);
3 ：f(0) , f(1) , ............ f(9)是常数存入一个cosnum数组中

   4 ：（F(10)）=    （A）  *    （F(9)）  这里的F区别于f ,  F(9)是一个常数矩阵
|f(10)|        |a0 a1 a2 ...a8 a9|    |f(9)|
| f(9) |        | 1  0  0 ... 0  0     |    |f(8)|
| .....   | =   |.. ... ... ... ..            |  *| .. |    = a0 * f(9) + a1 * f(8) + a2 * f(7) + …… + a9 * f(0);
| f(2) |       | 0  0  0 ... 0  0       |   |f(1)|
| f(1) |       | 0  0  0 ... 1  0       |   |f(0)|
由上面的等式可知F(11) = (A) * (F(10))  => (A)  *  ( (A)  *  F(9)) => (A)^2  *  (F(9))
我们就可以知道求F(K) = (A)^(K-9) * (F(9));就转化为矩阵的快速幂问题，只要求出A的K-9次幂矩阵，然后用求出的ans矩阵的第一行乘上F（9），我们用倒着乘cosnum即可，注意求sum时候的取模运算

代码：
[cpp]
#include <iostream> 
#include <cstdio> 
#include <cstring> 
#include <string> 
#include <queue> 
using namespace std; 
const long long MAXN = 10; 
 
long long k, mod, sum; 
long long num[MAXN][MAXN];//所需的矩阵 
long long cosnum[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};//常量数组 
 
class Matrix {  
public: 
    long long m[MAXN][MAXN];//public比较方便 
    Matrix() {} 
     
    //矩阵的数组初始化 
    void init(long long num[MAXN][MAXN]) { 
        for (int i = 0; i < MAXN; i++) { 
            for (int j = 0; j < MAXN; j++) { 
                m[i][j] = num[i][j]; 
            } 
        } 
    } 
     
    //重载矩阵的乘法运算 
    friend Matrix operator*(Matrix &m1, Matrix &m2) { 
        int i, j, k; 
        Matrix temp; 
        for (i = 0; i < MAXN; i++) { 
            for (j = 0; j < MAXN; j++) { 
                temp.m[i][j] = 0; 
                for (k = 0; k < MAXN; k++) 
                    temp.m[i][j] += (m1.m[i][k] * m2.m[k][j]) % mod; 
                temp.m[i][j] %= mod; 
            } 
        } 
        return temp; 
    } 
     
    //矩阵的快速幂 
    friend Matrix quickpow(Matrix &M, long long n) { 
        Matrix tempans;//（对于矩阵的快速幂）是单位矩阵 
        for (int i = 0; i < MAXN; i++) { 
            for (int j = 0; j < MAXN; j++) { 
                if (i == j) 
                    tempans.m[i][j] = 1; 
                else 
                    tempans.m[i][j] = 0; 
            } 
        } 
        //快速幂的运算 
        while (n) { 
            if (n & 1) 
                tempans = tempans * M; 
            n = n >> 1; 
            M = M * M; 
        } 
        return tempans; 
    } 
}; 
 
int main() { 
    Matrix A, ans; 
    while (scanf("%lld%lld/n", &k, &mod) != EOF) { 
        //初始化矩阵 
        memset(num, 0, sizeof (num)); 
        for (int i = 0; i < 10; i++) 
            scanf("%lld", &num[0][i]); 
        for (int i = 1; i < MAXN; i++) 
            num[i][i - 1] = 1; 
        //判断 
        if (k < 10) 
            printf("%lld/n", k % mod); 
        else { 
            A.init(num); //初始化A矩阵 
            ans = quickpow(A, k - 9); //求出矩阵的快速幂 
            //求和       www.2cto.com
            sum = 0; 
            for (int i = 0; i < MAXN; i++){ 
                sum += ((ans.m[0][i] * cosnum[MAXN-i-1]) % mod);//每一步都取模不影响结果 
                sum %= mod; 
            } 
            printf("%lld/n", sum); 
        }    
    } 
} 

作者：cgl1079743846