一个排队问题，f代表女，m代表男，f和m出现的几率相等。问一个长为L的队伍不能出现 fmf 和 fff这样的串总共有多少种。
这个题目的公式递推略难啊。。。我看了别人博客才想明白原来是这么递推出来的。
首先把前几项写出来。
L=0 ，ans=0；
L=1，ans=2；
L=2，ans=4；
L=3，ans=6；
L=4，ans=9；
规律有点难找，直接递推出来，假设 长度为n的串，n>4，ans[n] 无非就是在 ans[n-1]的基础上加一个 f或者m，如果在ans[n-1]的基础上在队列最后加一个m，则绝对合法，因为不论前面n-1个是怎么排列，最后加一个m，绝对不会构成fmf或者fff，所以 ans[n]+=f[n-1]; 但是如果最后一位加的是f，
就要分类讨论了:
这个时候，如果n-1位为m，则 n-2位一定要是m 也就是说 一定要 ans[n-3]+mmf才满足条件，于是ans[n]+=ans[n-3]
这个时候，如果n-1位为f，则n-2位必定为m（否则就后三位fff了）,不仅如此，第n-3位一定要是m（否则就fmf了），所以就要 ans[n-4]+mmff,所以ans+=ans[n-4];
所以最后的递推出来的公式就是 ans[n]=ans[n-1]+ans[n-3]+ans[n-4];
得此公式，构造出矩阵。。。凡是学过矩阵快速幂的应该都会写了。
#include <iostream> #include <cstdio> #include <cstring> using namespace std; int l,m; int date[6]; struct Mat{ int mat[5][5]; }; Mat s,E; Mat operator *(Mat a,Mat b) { Mat c; memset(c.mat,0,sizeof (Mat)); int i,j,k; for (i=0;i<4;i++) for (j=0;j<4;j++) for (k=0;k<4;k++) { if(a.mat[i][k] && b.mat[k][j]) c.mat[i][j]+=a.mat[i][k]*b.mat[k][j]; c.mat[i][j]%=m; } return c; } Mat operator ^(Mat a,int x) { Mat c=E; for (;x;x>>=1) { if (x&1) c=c*a; a=a*a; } return c; } void init() { date[0]=0; date[1]=2; date[2]=4; date[3]=6; date[4]=9; memset(s.mat,0,sizeof (Mat)); memset(E.mat,0,sizeof (Mat)); s.mat[0][0]=s.mat[0][2]=s.mat[0][3]=1; s.mat[1][0]=1; s.mat[2][1]=1; s.mat[3][2]=1; for (int i=0;i<4;i++) E.mat[i][i]=1; } int main() { init(); while (scanf("%d%d",&l,&m)!=EOF) { if (l<=4) { printf("%d ",date[l]%m); continue; } Mat ans; ans=s^(l-4); int sum=0; for (int i=0;i<4;i++) { sum+=ans.mat[0][i]*date[4-i]; } sum%=m; printf("%d ",sum); } return 0; }