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 
#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("%lld\n", ans % mod);}return 0;
}   

转载于:https://www.cnblogs.com/lykkk/p/10711406.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！