hdu 2604 Queuing 矩阵快速幂

57 阅读 0 评论 38 点赞

我是靠谱客的博主文艺发卡，最近开发中收集的这篇文章主要介绍hdu 2604 Queuing 矩阵快速幂，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

链接：http://acm.hdu.edu.cn/showproblem.php?pid=2604

题意：给出一个队列，其中站着f（女人）m（男人），让你求出队列中不含有fmf和fff的队列总共的种类数（对M取模）。队列长度达到1e6肯定不能用排列组合做，用状态转移的方式。因为要取模，所以不能打表，只能每次求，这样就需要用到矩阵快速幂来降低时间复杂度了。

递推公式：（a[i][0]~aa[i][3]分别代表mm,mf,fm,ff结尾的队列）

a[i][0]=a[i-1][2]+a[i-1][0]

a[i][1]=a[i-1][0]

a[i][2]=a[i-1][1]+a[i-1][3]

a[i][3]=a[i-1][1]

所以右乘矩阵 1 0 1 0 即可。

1 0 0 0

0 1 0 1

0 1 0 0

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <stdlib.h>
using namespace std;
#define maxn 10
int M,K;
struct Matrix
{
    int n,m;
    int a[maxn][maxn];
    Matrix operator *(const Matrix &b)const
    {
        Matrix tmp;
        tmp.n=n;
        tmp.m=m;
        memset(tmp.a,0,sizeof(tmp.a));
        for(int i=0; i<n; i++)
            for(int j=0; j<b.m; j++)
                for(int k=0; k<m; k++)
                {
                    tmp.a[i][j]+=a[i][k]*b.a[k][j];
                    tmp.a[i][j]%=M;
                }
        return tmp;
    }
};
Matrix M_quick_pow(Matrix &m,int k)
{
    Matrix tmp;
    tmp.n=m.n;
    tmp.m=m.m;
    for(int i=0; i<tmp.n; i++)
    {
        for(int j=0; j<tmp.n; j++)
        {
            if(i==j)
                tmp.a[i][j]=1;
            else tmp.a[i][j]=0;
        }
    }
    while(k)
    {
        if(k&1)
            tmp=tmp*m;
        k>>=1;
        m=m*m;
    }
    return tmp;
}
int main()
{
    while(scanf("%d%d",&K,&M)!=EOF)
    {
        Matrix aa;
        aa.n=aa.m=4;
        aa.a[0][0]=aa.a[0][2]=aa.a[1][0]=aa.a[2][1]=aa.a[2][3]=aa.a[3][1]=1;
        aa.a[0][1]=aa.a[0][3]=aa.a[1][1]=aa.a[1][2]=aa.a[1][3]=aa.a[2][0]=aa.a[2][2]=aa.a[3][0]=aa.a[3][2]=aa.a[3][3]=0;
        Matrix bb;
        bb.n=1,bb.m=4;
        bb.a[0][0]=bb.a[0][1]=bb.a[0][2]=bb.a[0][3]=1;
        aa=M_quick_pow(aa,K-2);
        bb=bb*aa;
        int ans=0;
        for(int i=0;i<4;i++)
        ans=(ans+bb.a[0][i])%M;
        printf("%dn",ans);

    }

}

本来做之前说建立矩阵如网络流建图一样困难，仔细想一想，没有那么困难，主要是找出递推公式，让后矩阵快速幂就是用来优化的。