题目大意：有2^L个长度为L的字符串，字符串只能有f或m组合而成，问这些字符串中不含有fmf或着fff的字符串有多少个
解题思路：设f(n)为字符串长度为n，且字符串中不包含fmf或者fff的字符串个数 假设现在填到第n位了，最后一个字符如果填的是m的话，那么f(n-1)的都可以填 最后一位填的如果是f的话，这就要考虑一下了，最后三位的话只可能是mmf,mff,fff,fmf,排除掉fff,fmf，就只剩下两种情况 如果最后是mmf的话，那么f(n-3)的都可以填 如果最后是mff的话，再考虑一位，那么最后可以填充的就变成了fmff,mmff排除掉fmff 最后如果是mmff的，，那么f(n-4)的都可以填 所以可得f(n) = f(n-1) + f(n-3) + f(n-4) 调用一下GG学长的图：
;const int N = 4;ll;struct Matrix{ll mat[N][N];}a, b, tmp;int L, M;void init() {for(int i = 0; i < N; i++)for(int j = 0; j < N; j++)a.mat[i][j] = b.mat[i][j] = 0;for(int i = 0; i < N; i++)b.mat[i][i] = 1;for(int i = 1; i < N; i++)a.mat[i][i-1] = 1;a.mat[0][0] = a.mat[0][2] = a.mat[0][3] = 1;}Matrix matrixMul(Matrix x, Matrix y) {for(int i = 0; i < N; i++)for(int j = 0; j < N; j++) {tmp.mat[i][j] = 0;for(int k = 0; k < N; k++)tmp.mat[i][j] += (x.mat[i][k] * y.mat[k][j]) % M;}return tmp;}void solve() {while(L) {if(L & 1)b = matrixMul(b,a);a = matrixMul(a,a);L >>= 1;}}int main() {while(scanf(“%d%d”, &L, &M) != EOF) {init();if(L <= 4) {switch(L) {case 1: printf(“%d\n”, 2 % M);break;case 2: printf(“%d\n”, 4 % M);break;case 3: printf(“%d\n”, 6 % M);break;case 4: printf(“%d\n”, 9 % M);}continue;}L -= 4;solve();printf(“%I64d\n”, (b.mat[0][0] * 9 + b.mat[0][1] * 6 + b.mat[0][2] * 4 + b.mat[0][3] * 2) % M);}return 0;}
在乎的是看风景的心情，旅行不会因为美丽的风景终止。
