题意:有长度为L的队,每个位置不是男的就是女的,用01表示,问有多少种排列方式不包含000和010这两种状态。
思路:最开始是想dp的,dp[i][j]表示前i个人以状态j为结尾的满足条件的排列方式,但是写完以后MLE……无语。。。只好写矩阵乘法,受到dp的启发,我们可以想到这么构造矩阵,当前位置分别以状态00,01,10,11结尾,再添加一个字符会转移到下一个状态,如果转移是合法的,那么对应位置是1,否则是0。这个和之前做过的一个AC自动机的有点像。矩阵构造出来以后就简单了,矩阵快速幂搞定。
代码:
#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<algorithm> #include<map> #include<queue> #include<set> #include<stack> #include<cmath> #include<vector> #define inf 0x3f3f3f3f #define Inf 0x3FFFFFFFFFFFFFFFLL #define eps 1e-9 #define pi acos(-1.0) using namespace std; typedef long long ll; struct Matrix { int mat[4][4]; void init() { for(int i=0;i<4;++i) for(int j=0;j<4;++j) mat[i][j]=(i==j); } void clear(){memset(mat,0,sizeof(mat));} }; int m; Matrix operator *(const Matrix &a,const Matrix &b) { Matrix c;c.clear(); for(int k=0;k<4;++k) for(int i=0;i<4;++i) for(int j=0;j<4;++j) c.mat[i][j]=(c.mat[i][j]+a.mat[i][k]*b.mat[k][j])%m; return c; } int solve(int n) { if(n==0) return 0; if(n==1) return 2%m; if(n==2) return 4%m; Matrix x,y; x.init();y.clear(); for(int i=0;i<4;++i) for(int j=0;j<4;++j) { if((i&1)!=(j>>1)) continue; int st=(i<<1)|j; if(st!=0&&st!=2) y.mat[i][j]=1; } n-=2; while(n) { if(n&1) x=x*y; y=y*y; n>>=1; } int ans=0; for(int i=0;i<4;++i) for(int j=0;j<4;++j) ans=(ans+x.mat[i][j])%m; return ans; } int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); int L; while(~scanf("%d%d",&L,&m)) { printf("%d\n",solve(L)); } return 0; }