题目链接：hdu2604

这题重要的递推公式，找到公式就很easy了（这道题和hdu1757(题解)类似，只是这道题需要自己推公式）

可以直接找规律，推出递推公式，也有另一种找递推公式的方法：(PS:在别的博客粘过来，暂时还不太理解。。。)

设f(n)为字符串长度为n时复合条件的字符串个数，以字符串最后一个字符为分界点，当最后一个字符为m时前n-1个字符没有限制，即为f(n-1)；当最后一个字符为f时就必须去除最后3个字符是fmf和fff的情况,在考虑最后两个字符为mf和ff的情况，显然不行；最后3个字符为fmf、mmf和fff、mff时只有当最后3个字符为mmf时前n-3个字符没有限制，即为f(n-3)，当为mff时第n-3个字符可能为f因而对前n-3个字符串有限制；最后4个字符为fmff和mmff时mmff可行。这样就讨论完了字符串的构成情况，得出结论：
f(n)=f(n-1)+f(n-3)+f(n-4)

然后用矩阵快速幂就OK了~~

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#include <cstdlib>

using namespace std;

int n,mod;

int a[6] = {1,2,4,6,9,15};

struct node

{

    int map[4][4];

}unit,s;

void initial()//初始化

{

    int i;

    memset(s.map,0,sizeof(node));

    for(i = 1; i < 4; i ++)

    s.map[i][i-1] = 1;

    s.map[0][0] = s.map[0][2] = s.map[0][3] = 1;

    memset(unit.map,0,sizeof(node));

    for(i = 0; i < 4; i ++)//单位矩阵

    unit.map[i][i] = 1;

}

node Mul(node a,node b)

{

    node c;

    int i,j,k;

    for(i = 0; i < 4; i ++)

    for(j = 0; j < 4; j ++)

    {

        c.map[i][j] = 0;

        for(k = 0; k < 4; k ++)

        c.map[i][j] += (a.map[i][k]*b.map[k][j])%mod;

        c.map[i][j] %= mod;

    }

    return c;

}

void Matrix()

{

    while(n)

    {

        if(n&1) unit = Mul(unit,s);

        n >>= 1;

        s = Mul(s,s);

    }

    int ans = 0;

    for(int i = 0; i < 4; i ++)

    ans += (unit.map[0][i]*a[5-i])%mod;

    printf("%d\n",ans%mod);

}

int main()

{

    while(~scanf("%d%d",&n,&mod))

    {

        if(n <= 5)

        {

            printf("%d\n",a[n]%mod);

            continue;

        }

        n -= 5;

        initial();

        Matrix();

    }

    return 0;

}