HDU 1757A Simple Math Problem(矩阵快速幂　简单题

题目来源：http://acm.hdu.edu.cn/showproblem.php?pid=1757

题目描述：

题意：

$F\left(n\right)=\{\begin{array}{cccc}F\left(n\right)=& n,& & n\&lt;10\\ F\left(n\right)=& {\sum }_{i=0}^{9}ai\times F(n-i-1),& & n\ge 10\end{array}$F(n)={F(n)=F(n)=​n,∑i=09​ai×F(n−i−1),​​n<10n≥10​
$\therefore ans=A^{n-9}\times B$∴ans=An−9×B
$\because \left\{\begin{array}{c}F\left(n\right)\\ F(n-1)\\ F(n-2)\\ F(n-3)\\ F(n-4)\\ F(n-5)\\ F(n-6)\\ F(n-7)\\ F(n-8)\\ F(n-9)\end{array}\right\}={\left\{\begin{array}{cccccccccc}{a}_0& a_1& a_2& a_3& a_4& a_5& a_6& a_7& a_8& a_9\\ 1& 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 1& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 1& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 1& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 1& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 1& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 1& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 1& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 0& 1& 0\end{array}\right\}}^{n-9}\times \left\{\begin{array}{c}F\left(9\right)\\ F\left(8\right)\\ F\left(7\right)\\ F\left(6\right)\\ F\left(5\right)\\ F\left(4\right)\\ F\left(3\right)\\ F\left(2\right)\\ F\left(1\right)\\ F\left(0\right)\end{array}\right\}$∵⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧​F(n)F(n−1)F(n−2)F(n−3)F(n−4)F(n−5)F(n−6)F(n−7)F(n−8)F(n−9)​⎭⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎬⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎫​=⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧​a0​100000000​a1​010000000​a2​001000000​a3​000100000​a4​000010000​a5​000001000​a6​000000100​a7​000000010​a8​000000001​a9​000000000​⎭⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎬⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎫​n−9×⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧​F(9)F(8)F(7)F(6)F(5)F(4)F(3)F(2)F(1)F(0)​⎭⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎬⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎫​
$\therefore B=\left\{\begin{array}{c}9\\ 8\\ 7\\ 6\\ 5\\ 4\\ 3\\ 2\\ 1\\ 0\end{array}\right\}，A=\left\{\begin{array}{cccccccccc}{a}_0& a_1& a_2& a_3& a_4& a_5& a_6& a_7& a_8& a_9\\ 1& 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 1& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 1& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 1& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 1& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 1& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 1& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 1& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 0& 1& 0\end{array}\right\}$∴B=⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧​9876543210​⎭⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎬⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎫​，A=⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧​a0​100000000​a1​010000000​a2​001000000​a3​000100000​a4​000010000​a5​000001000​a6​000000100​a7​000000010​a8​000000001​a9​000000000​⎭⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎬⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎫​

参考代码：

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
#define ll long long
#define endl '\n'
#define mem(a,b) memset(a,b,sizeof(a))
const ll N=10;
ll k,mod;
struct Matrix {
    ll m[N][N];

    Matrix() {
        mem(m, 0);
    }

    void init() {
        for (int i = 0; i < N; i++)m[i][i] = 1;
    }

    Matrix operator+(const Matrix &b) const {
        Matrix c;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                c.m[i][j] = (m[i][j] + b.m[i][j]) % mod;
            }
        }
        return c;
    }

    Matrix operator*(const Matrix &b) const {
        Matrix c;
        mem(c.m,0);
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                for (int k = 0; k < N; k++) {
                    c.m[i][j] = (c.m[i][j] + (m[i][k] * b.m[k][j]) % mod) % mod;
                }
            }
        }
        return c;
    }

    Matrix operator^(const ll &t) const {
        Matrix ans, a = (*this);
        ans.init();
        ll n = t;
        while (n) {
            if (n & 1) ans = ans * a;
            a = a * a;
            n >>= 1;
        }
        return ans;
    }
};
int main() {
    while (~scanf("%lld%lld", &k, &mod)) {
        Matrix A;
        mem(A.m, 0);
        Matrix B;
        mem(B.m, 0);
        for (int i = 0; i < N; i++) {
            scanf("%lld", &A.m[0][i]);
        }
        if (k < 10) {
            printf("%lld\n", A.m[0][k] % mod);
            continue;
        }
        for(int i=0;i<N;i++){
            B.m[9-i][0]=i;
        }
        for (int i = 1; i < N; i++) {
            A.m[i][i - 1] = 1;
        }
        Matrix ans = (A ^ (k - 9)) * B;
        printf("%lld\n", ans.m[0][0] % mod);
    }
    return 0;
}