hdu 2604 Queuing（动态规划—>矩阵快速幂,更通用的模版）

题目

最早不会写，看了网上的分析，然后终于想明白了矩阵是怎么出来的了，哈哈哈哈。

因为边上的项目排列顺序不一样，所以写出来的矩阵形式也可能不一样，但是都是可以的

//愚钝的我不会写这题，然后百度了，照着大神的题解，有了如下的东东:
//根据ff, mm, fm, mf ，先列出所有可能的组合方式(1表示连在一次，具体判断方式自己看看就知道了)
//  ff mm fm mf
//ff 1  0  1  0
//mm 0  1  0  1
//fm 0  1  0  1
//mf 1  0  1  0
//题目中说不能有fff和fmf，所以去掉他们，最终结果如下
//  ff mm fm mf
//ff 0  0  1  0
//mm 0  1  0  1
//fm 0  1  0  0
//mf 1  0  1  0
#include<stdio.h>
#include<string.h>
int num=4,mod;
struct matrix
{
    int a[4][4];
}answ;
matrix multiply(matrix x,matrix y)//矩阵乘法
{
    matrix temp;
    memset(temp.a,0,sizeof(temp.a));
    for(int i=0;i<num;i++)
    {
        for(int k=0;k<num;k++)
        {
            for(int j=0;j<num;j++)
            {
                temp.a[i][j]=(temp.a[i][j]+x.a[i][k]*y.a[k][j])%mod;
            }
        }
    }
    return temp;
}
matrix calc(matrix a,int n)//矩阵快速幂——a^n
{
    if(n==1)return a;
    matrix e;
    for(int i=0;i<num;i++)
        for(int j=0;j<num;j++)
            e.a[i][j]=(i==j);

    while(n)
    {
        if(n&1)
            e=multiply(e,a);
        n>>=1;
        a=multiply(a,a);
    }
    return e;
}
int main()
{
    int n,sum;
    while(scanf("%d%d",&n,&mod)!=EOF)
    {
        sum=0;
        matrix origin= {0,0,1,0,
                        0,1,0,1,
                        0,1,0,0,
                        1,0,1,0};
        answ=calc(origin,n-2);//因为给的项目是后两位
        for(int i=0;i<4;i++)
            for(int j=0;j<4;j++)
                sum=(sum+answ.a[i][j])%mod;
        printf("%d
",sum);
    }
    return 0;
}