Queuing(HDOJ 2604)
Problem Description
Queues and Priority Queues are data structures which are known to most computer scientists. The Queue occurs often in our daily life. There are many people lined up at the lunch time.
Now we define that ‘f’ is short for female and ‘m’ is short for male. If the queue’s length is L, then there are 2ᴸ numbers of queues. For example, if L = 2, then they are ff, mm, fm, mf . If there exists a subqueue as fmf or fff, we call it O-queue else it is a E-queue.
Your task is to calculate the number of E-queues mod M with length L by writing a program.
Input
Input a length L (0 <= L <= 10 6) and M.
Output
Output K mod M(1 <= M <= 30) where K is the number of E-queues with length L.
Sample Input
3 8 4 7 4 8
Sample Output
6 2 1
My Code
这题关键是求出递推式，之后就是利用矩阵 快速幂来计算了。至于如何算递推式，就是一个排列组合的问题了，首先需要知道包含fmf和fff是不合法的，而他们都是以f结尾的，所以在合法序列之后加一个m依旧是合法序列，因此递推式里先加一个an-1 。然后末位是f的话，末两位有mf和ff两种情况，如果是mf结尾，那么倒数第三位就必须是m否则就是不合法的了，由于之前说过，合法序列末位加上一个m，还是合法序列，所以由此可得加上mmf依旧是合法序列，递推式里再加上一个an-3 。然后是末两位是ff的话，那么倒数第三位只能是m，否则就是fff不合法了，因此末三位就是mff，但这样的话如果倒数第四位是f，就会产生fmf，所以倒数第四位就必须是m，这样同理可得合法序列后面加mmff还是合法序列。这样就得到了递推式an = an-1 +an-3 +an-4 。之后就是构造矩阵来算递推式了，这个学过线代的话，应该看得懂，看不懂的话，画个矩阵人工模拟一下就知道了。
#include
#include
using namespace std;
int mod;
struct Matrix
{
int M[5][5];
};
Matrix mul(Matrix m1, Matrix m2, int n)
{
Matrix m3;
memset(m3.M, 0, sizeof(m3.M));
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
{
for (int k = 0; k < n; k++)
m3.M[i][j] += (m1.M[i][k] * m2.M[k][j]) % mod;
m3.M[i][j] %= mod;
}
return m3;
}
Matrix pow(Matrix m, int k, int n)
{
Matrix ans;
memset(ans.M, 0, sizeof(ans.M));
for (int i = 0; i < n; i++)
ans.M[i][i] = 1;
while (k)
{
if (k & 1)
ans = mul(ans, m, n);
m = mul(m, m, n);
k >>= 1;
}
return ans;
}
int main()
{
int n, k;
Matrix m;
Matrix ans;
ans.M[0][0] = 9;
ans.M[1][0] = 6;
ans.M[2][0] = 4;
ans.M[3][0] = 2;
while (cin >> n >> mod)
{
memset(m.M, 0, sizeof(m.M));
m.M[0][0] = m.M[0][2] = m.M[0][3] = 1; //利用矩阵快速幂来算递推式
m.M[1][0] = m.M[2][1] = m.M[3][2] = 1; //F(n)=F(n-1)+F(n-3)+F(n-4)
if (n < 5)
cout << ans.M[4 - n][0] % mod << endl; //这边也要记得mod
else
cout << mul(pow(m, n - 4, 4), ans, 4).M[0][0] << endl;
}
return 0;
} 
OωO
