现在的位置: 首页 > 综合 > 正文

hdu 2604 Queuing(矩阵乘法)

2014年08月29日 ⁄ 综合 ⁄ 共 1331字 ⁄ 字号 评论关闭

题意:有长度为L的队,每个位置不是男的就是女的,用01表示,问有多少种排列方式不包含000和010这两种状态。

思路:最开始是想dp的,dp[i][j]表示前i个人以状态j为结尾的满足条件的排列方式,但是写完以后MLE……无语。。。只好写矩阵乘法,受到dp的启发,我们可以想到这么构造矩阵,当前位置分别以状态00,01,10,11结尾,再添加一个字符会转移到下一个状态,如果转移是合法的,那么对应位置是1,否则是0。这个和之前做过的一个AC自动机的有点像。矩阵构造出来以后就简单了,矩阵快速幂搞定。

代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<cmath>
#include<vector>
#define inf 0x3f3f3f3f
#define Inf 0x3FFFFFFFFFFFFFFFLL
#define eps 1e-9
#define pi acos(-1.0)
using namespace std;
typedef long long ll;
struct Matrix
{
    int mat[4][4];
    void init()
    {
        for(int i=0;i<4;++i)
            for(int j=0;j<4;++j)
                mat[i][j]=(i==j);
    }
    void clear(){memset(mat,0,sizeof(mat));}
};
int m;
Matrix operator *(const Matrix &a,const Matrix &b)
{
    Matrix c;c.clear();
    for(int k=0;k<4;++k)
        for(int i=0;i<4;++i)
            for(int j=0;j<4;++j)
                c.mat[i][j]=(c.mat[i][j]+a.mat[i][k]*b.mat[k][j])%m;
    return c;
}
int solve(int n)
{
    if(n==0) return 0;
    if(n==1) return 2%m;
    if(n==2) return 4%m;
    Matrix x,y;
    x.init();y.clear();
    for(int i=0;i<4;++i)
        for(int j=0;j<4;++j)
        {
            if((i&1)!=(j>>1)) continue;
            int st=(i<<1)|j;
            if(st!=0&&st!=2)
                y.mat[i][j]=1;
        }
    n-=2;
    while(n)
    {
        if(n&1) x=x*y;
        y=y*y;
        n>>=1;
    }
    int ans=0;
    for(int i=0;i<4;++i)
        for(int j=0;j<4;++j)
            ans=(ans+x.mat[i][j])%m;
    return ans;
}
int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int L;
    while(~scanf("%d%d",&L,&m))
    {
        printf("%d\n",solve(L));
    }
    return 0;
}

抱歉!评论已关闭.