HDU 2604 Queuing

矩阵快速幂

传送门：HUSTOJ

传送门：HDU

---

题意

n个人排队，f表示女，m表示男，包含子串‘fmf’和‘fff’的序列为O队列，否则为E队列，有多少个序列为E队列。

---

思路

矩阵快速幂搞，递推会挂。 板子。 %%%1 %%%2

---

代码

我竟然忘了矩阵乘法不可交换。。

#include<cstdio> #include<cstdlib> #include<iostream> #include<algorithm> #include<string> #include<cstring> #include<vector> #include<cmath> #include<queue> #define _ ios_base::sync_with_stdio(0);cin.tie(0); using namespace std; const int MAXN=4; const int oo=0x3f3f3f3f; typedef long long LL; const LL loo=4223372036854775807ll; int MOD=0; struct Matrix { int ma[MAXN][MAXN]; Matrix(){ memset(ma, 0, sizeof(ma)); } Matrix(Matrix &a) { for(int i=0;i<MAXN;i++) { for(int j=0;j<MAXN;j++) { ma[i][j]=a.ma[i][j]; } } } }; Matrix operator *(Matrix &a, Matrix &b) { Matrix c; for(int i=0;i<MAXN;i++) { for(int j=0;j<MAXN;j++) { for(int k=0;k<MAXN;k++) { c.ma[i][j]=(c.ma[i][j]+(a.ma[i][k]*b.ma[k][j])%MOD)%MOD; } } } return c; } Matrix operator ^(Matrix &a, int m) { Matrix t; for(int i=0;i<MAXN;i++) t.ma[i][i]=1; while(m) { if(m&1) t=a*t; a=a*a; m>>=1; } return t; } int main() {_ int L; while(cin>>L>>MOD) { Matrix a, b, c; a.ma[0][0]=9;a.ma[1][0]=6;a.ma[2][0]=4;a.ma[3][0]=2; b.ma[0][0]=b.ma[0][2]=b.ma[0][3]=b.ma[1][0]=b.ma[2][1]=b.ma[3][2]=1; if(L==0) cout<<0<<endl; else if(L<=4) cout<<a.ma[4-L][0]%MOD<<endl; else { L-=4; c=b^L; c=c*a; cout<<c.ma[0][0]<<endl; } } //system("pause"); return 0; }