HDU_2604 矩阵快速幂较难推的公式

一个排队问题，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[];

struct Mat{

    int mat[][];

};

Mat s,E;

Mat operator *(Mat a,Mat b)

{

    Mat c;

    memset(c.mat,,sizeof (Mat));

    int i,j,k;

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

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

        for (k=;k<;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>>=)

    {

        if (x&)

            c=c*a;

        a=a*a;

    }

    return c;

}

void init()

{

    date[]=;

    date[]=;

    date[]=;

    date[]=;

    date[]=;

    memset(s.mat,,sizeof (Mat));

    memset(E.mat,,sizeof (Mat));

    s.mat[][]=s.mat[][]=s.mat[][]=;

    s.mat[][]=;

    s.mat[][]=;

    s.mat[][]=;

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

        E.mat[i][i]=;

}

int main()

{

    init();

    while (scanf("%d%d",&l,&m)!=EOF)

    {

        if (l<=)

        {

            printf("%d\n",date[l]%m);

            continue;

        }

        Mat ans;

        ans=s^(l-);

        int sum=;

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

        {

            sum+=ans.mat[][i]*date[-i];

        }

        sum%=m;

        printf("%d\n",sum);

    }

    return ;

}

巴特西

HDU_2604 矩阵快速幂较难推的公式

最新文章

热门文章

巴特西

HDU_2604 矩阵快速幂 较难推的公式

最新文章

热门文章

HDU_2604 矩阵快速幂较难推的公式