HDU - 2604　Queuing（矩阵快速幂，推规律

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

题目描述：

题意：

由f和m构成一个长度为L的序列，求不存在fmf和fff的串的方案数，答案对mod取余。

思路：

通过列出前６项，F(1)=2,F(2)=4,F(3)=6,F(4)=9,F(5)=15,F(6)=25…
从而推出公式F(n)=F(n-1)+F(n-3)+F(n-4)
从而得到中间矩阵A, 答案(F(n))就是 Matrix ans = $A^{n-4}\times B$An−4×B的第一项 :ans.m[0][0]
**ps:L为０的时候答案是０ **
$\because \left\{\begin{array}{c}F(n-1)\\ F(n-2)\\ F(n-3)\\ F(n-4)\end{array}\right\}\times A=\left\{\begin{array}{c}F\left(n\right)\\ F(n-1)\\ F(n-2)\\ F(n-3)\end{array}\right\}$∵⎩⎪⎪⎨⎪⎪⎧​F(n−1)F(n−2)F(n−3)F(n−4)​⎭⎪⎪⎬⎪⎪⎫​×A=⎩⎪⎪⎨⎪⎪⎧​F(n)F(n−1)F(n−2)F(n−3)​⎭⎪⎪⎬⎪⎪⎫​
$又\because \left\{\begin{array}{c}F(n-1)\\ F(n-2)\\ F(n-3)\\ F(n-4)\end{array}\right\}\times \left\{\begin{array}{cccc}1& 0& 1& 1\\ 1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& 1& 0\end{array}\right\}=\left\{\begin{array}{c}F\left(n\right)\\ F(n-1)\\ F(n-2)\\ F(n-3)\end{array}\right\}$又∵⎩⎪⎪⎨⎪⎪⎧​F(n−1)F(n−2)F(n−3)F(n−4)​⎭⎪⎪⎬⎪⎪⎫​×⎩⎪⎪⎨⎪⎪⎧​1100​0010​1001​1000​⎭⎪⎪⎬⎪⎪⎫​=⎩⎪⎪⎨⎪⎪⎧​F(n)F(n−1)F(n−2)F(n−3)​⎭⎪⎪⎬⎪⎪⎫​
$\therefore A=\left\{\begin{array}{cccc}1& 0& 1& 1\\ 1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& 1& 0\end{array}\right\}$∴A=⎩⎪⎪⎨⎪⎪⎧​1100​0010​1001​1000​⎭⎪⎪⎬⎪⎪⎫​
$B=\left\{\begin{array}{c}F\left(4\right)=9\\ F\left(3\right)=6\\ F\left(2\right)=4\\ F\left(1\right)=2\end{array}\right\}$B=⎩⎪⎪⎨⎪⎪⎧​F(4)=9F(3)=6F(2)=4F(1)=2​⎭⎪⎪⎬⎪⎪⎫​

参考代码：

#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=4;
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)) {
        if (k == 0) {
            printf("0\n");
        } else if (k == 1) {
            printf("%d\n",2%mod);
        } else if (k == 2) {
            printf("%d\n",4%mod);
        } else if (k == 3) {
            printf("%d\n",6%mod);
        } else if (k == 4) {
            printf("%d\n",9%mod);
        } else {
            Matrix A;
            mem(A.m, 0);
            A.m[0][0] = A.m[0][2] = A.m[0][3] = 1;
            Matrix B;
            mem(B.m, 0);
            for (int i = 1; i < N; i++) {
                A.m[i][i - 1] = 1;
            }
            B.m[0][0] = 9, B.m[1][0] = 6, B.m[2][0] = 4, B.m[3][0] = 2;
            Matrix ans = (A ^ (k - 4)) * B;
            printf("%lld\n", ans.m[0][0] % mod);
        }
    }
    return 0;
}