HDU 2604 Queuing (矩阵快速幂)

题目

HDU 2604 Queuing
题意： 给你一个数(L)代表一个队的长度，男女不限，随便排，(f)代表女生，(m)代表男生，但是其中不能出现(fmf),(fff) 这种子序列，问一共有多少种排的方法，结果需要(mod m).

解析：

构思巧妙的一道矩阵快速幂
我们设(f[i])表示有(i)个人时有多少种方案。
我们考虑第(n)个位置

• 假设第(n)位为(m)，那前(n-1)位是什么都行，有(f[n-1])种方案。
• 假设第(n)位为(f)，就有两种情况
  1. 第(n-1)位为(m)，那(n-2)位上一定要为(m)，第(n-3)位上就是随便选了，有(f[n-3])种方案
  2. 第(n-1)位为(f)，那(n-2)位一定要为(m)，且第(n-3)位上也要为(m)，那第(n-4)位就随便选了，有(f[n-4])

综上所述，(f[n]=f[n-1]+f[n-3]+f[n-4])
然后考虑矩阵加速
[begin{bmatrix} 1&0&1&1\ 1&0&0&0\ 0&1&0&0\ 0&0&1&0\ end{bmatrix}^{n-4}begin{bmatrix}f_4\f_3\f_2\f_1 end{bmatrix}=begin{bmatrix}f_n\f_{n-1}\f_{n-2}\f_{n-3} end{bmatrix}]
然后套矩阵快速幂就完了

代码

//矩阵快速幂 
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 10;
int n, mod;
int f[N] = {0, 2, 4, 6, 9};
class matrix {
    public :
        int a[N][N];
        matrix() {
            memset(a, 0, sizeof (a));
        }
        void initialize() {
            memset(a, 0, sizeof(a));
            a[1][1] = a[1][3] = a[1][4] = a[2][1] = a[3][2] = a[4][3] = 1;
            
        }
        matrix operator * (const matrix & oth) const {
            matrix ret;
            for (int i = 1; i <= 4; ++i)
                for (int j = 1; j <= 4; ++j)
                    for (int k = 1; k <= 4; ++k)
                        ret.a[i][j] = (ret.a[i][j] % mod + (this->a[i][k] * oth.a[k][j]) % mod) % mod;
            return ret;         
        }
} init; 

matrix qpow(matrix a, int b) {
    matrix ans = init;
    while (b) {
        if (b & 1) ans = ans * a;
        b >>= 1, a = a * a;
    }
    return ans;
}


signed main() {
    while (scanf("%lld%lld", &n, &mod) != EOF) {
        if (n <= 4) {
            printf("%d", f[n] % mod);
            continue;
        }
        init.initialize();
        init = qpow(init, n - 5);
        int ans = 0;
        for (int i = 1; i <= 4; ++i)
            ans += init.a[1][i] * f[4 - i + 1] % mod;
        printf("%lldn", ans % mod);
    }
    return 0;
}