|
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 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 |
这题我的思路与其他人不太一样 但是大同小异。
L mf mm fm ff
2 1 1 1 1
3 1 2 2 1
令mf、mm、fm、ff分别为a,b,c,d;
可以看出a(n)=b(n-1); b(n)=b(n-1)+c(n-1); c(n)=a(n-1)+d(n-1);d(n)=a(n-1);
由于题目限制简单地递推会T，不能满足要求
这里把abcd看作一个矩阵
b c * 1 1 = b+c(b‘) b(a‘)
a d 1 0 a+d(c‘) a(d‘)
1 1 * b a = b+c(b‘) a+d(c‘)
1 0 c d b(a‘) a(d‘)
通过右乘、左乘（1，1，1，0）矩阵；达到递推的效果
然后用二分快速幂的方法解题
代码如下：
#include<stdio.h>
#define L(i) for(int i=0;i<2;i++)
int m;
void multip3(int t[2][2]){
int x[2][2];
L(i) L(j){
x[i][j]=0;
L(k) x[i][j]+=(t[i][k]*t[k][j])%m;
x[i][j]=x[i][j]%m;
}
L(i)L(j) t[i][j]=x[i][j];
}
void mulleft(int a[2][2],int t[2][2]){
int x[2][2];
x[0][0]=a[0][0]; x[0][1]=a[1][0];
x[1][0]=a[0][1]; x[1][1]=a[1][1];
L(i) L(j){
a[i][j]=0;
L(k)a[i][j]+=(x[j][k]*t[k][i])%m;
a[i][j]=a[i][j]%m;
}
}
void mulright(int a[2][2],int t[2][2]){
int x[2][2];
x[0][0]=a[0][0]; x[0][1]=a[1][0];
x[1][0]=a[0][1]; x[1][1]=a[1][1];
L(i)L(j){
a[i][j]=0;
L(k)a[i][j]+=(x[i][k]*t[k][j])%m;
a[i][j]=a[i][j]%m;
}
}
int z[30][2][2];
int main(){
int L;
while(scanf("%d%d",&L,&m)!=EOF){
int x=0;
if(L==0) printf("0\n");
else if(L==1) printf("%d\n",2%m);
else if(L==2) printf("%d\n",4%m);
else{
L-=2;
int xxx=0;
if(L%2==1) {xxx=1;}
L/=2;
int t[2][2]={1,1,1,0};
for(int i=0;i<=25;i++){
L(j)L(k) z[i][j][k]=t[j][k];
multip3(t);
}
int k=0,xx=1;
int x1[2][2]={1,1,1,1};
if(xxx){
x1[0][0]=2;x1[0][1]=1;
x1[1][0]=2;x1[1][1]=1;
}
while(L!=0){
if(L%2==1) {mulright(x1,z[k]);mulleft(x1,z[k]);}
L/=2;k++;
}
xx=(x1[0][0]+x1[1][0]+x1[0][1]+x1[1][1])%m;
printf("%d\n",xx);
}
}
return 0;
}
第一次写这种题目
很开心~~~
原文：http://www.cnblogs.com/liujiaqi-Boke/p/5475539.html