HDU - 2604 -- Queuing【矩阵快速幂+DP】

Queuing

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 2L 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

思路

本题关键还是能找到关系式，然后构造核心矩阵，如果不会构造核心矩阵，这篇文章可能会帮助你
如何构造核心矩阵

AC代码

#include
#include
#include
using namespace std;
typedef long long ll;
struct Mat{ll m[10][10];
}arr,A;
int L,mod;
int f[5]={0,2,4,6,9};
Mat operator *(Mat a,Mat b){Mat temp;memset(temp.m,0,sizeof(temp.m));for(int i=0;i<4;i++)for(int j=0;j<4;j++)for(int k=0;k<4;k++)temp.m[i][j]=(temp.m[i][j] + a.m[i][k] * b.m[k][j] % mod) % mod;return temp;
}
Mat fast_power(Mat a,int b){Mat res;memset(res.m,0,sizeof(res.m));for(int i=0;i<4;i++)	res.m[i][i]=1;while(b>0){if(b&1)	res = res*a;a = a*a;b>>=1;}return res;
}
void init(){//(f(4),f(3),f(2),f(1))memset(arr.m,0,sizeof(arr.m));arr.m[0][0]=f[4];arr.m[0][1]=f[3];arr.m[0][2]=f[2];arr.m[0][3]=f[1];memset(A.m,0,sizeof(A.m));A.m[0][0]=A.m[0][1]=A.m[1][2]=A.m[2][0]=A.m[2][3]=A.m[3][0]=1;
}
int main(){while(scanf("%d%d",&L,&mod)!=EOF){if(L<=4){printf("%d\n",f[L]%mod);continue;}init();Mat D = fast_power(A,L-4);Mat ans = arr*D;printf("%lld\n",ans.m[0][0]);}return 0;
}

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