http://acm.hdu.edu.cn/showproblem.php?pid=2604

Queuing

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 8567    Accepted Submission(s): 3749

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.
矩阵快速幂(queue递推)-LMLPHP
  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 ) 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
 
Author
WhereIsHeroFrom
 
Source
 
Recommend
lcy   |   We have carefully selected several similar problems for you:  1588 2606 2276 2603 3117
 
题意:有2的L次方个组合队列,求出不包含子序列fmf和fff的个数;
思路:根据长度增长变化可发现,fn就是在f(n-1)已知序列后加上f或m变化而来。根据题意可推出
递推式:
fn     0 1 2 1 2    f(n-1)
ff      0 0 0 0 1    ff(子序列的数量)
mm    0 0 1 1 0    mm
fm      0 1 0 0 1    fm
mf      0 0 1 0 0    mf
 
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <algorithm>
#include <iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include <stdio.h>
#include <string.h>
#include <vector>
#define ME(x , y) memset(x , y , sizeof(x))
#define SF(n) scanf("%d" , &n)
#define rep(i , n) for(int i = 0 ; i < n ; i ++)
#define INF 0x3f3f3f3f
//#define mod 1000000009
using namespace std;
typedef long long ll ;
ll n , mod ;
struct node{
ll a[][];
}; node mul(node A , node B)
{
node C ;
memset(C.a , , sizeof(C.a));
for(int i = ; i < ; i++)
{
for(int j = ; j < ; j++)
{
for(int k = ; k < ; k++)
{
C.a[i][j] = (C.a[i][j] + A.a[i][k] * B.a[k][j]) % mod;
}
}
}
return C;
} node pow(node A , ll n)
{
node ans ;
memset(ans.a , ,sizeof(ans.a));
for(int i = ;i < ; i++)
ans.a[i][i] = ;
while(n)
{
if(n & )
{
ans = mul(ans , A);
}
n >>= ;
A = mul(A , A);
}
return ans ;
} int main()
{
while(~scanf("%lld%lld" , &n , &mod))
{
node A , B , C ;
memset(A.a , , sizeof(A.a));
A.a[][] = , A.a[][] = ,A.a[][] = ,A.a[][] = ;
A.a[][] = , A.a[][] = ,A.a[][] = ,A.a[][] = ;
A.a[][] = , A.a[][] = ; B.a[][] = , B.a[][] = , B.a[][] = , B.a[][] = ;
B.a[][] = ; C = mul(pow(A , n-) , B);
printf("%lld\n" , C.a[][]);
} return ;
}

不过这道题还有别的递推式:

递推方程:f(n)=f(n-1)+f(n-3)+f(n-4)。

  如果第n位是f,它前面是f时(ff),再前一位必须是m(mff),再前一位还必须是m(mmff),所以有f(n-4)种;

         它前面是m时(mf),再前一位必须是m(mmf),再前就任意了,所以有f(n-3)种

  第n位是m,它前面可以是任意的,所以有f(n-1)种。

  接下来是构造矩阵:

矩阵快速幂(queue递推)-LMLPHP

05-11 21:54
查看更多