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