BZOJ1898 [ZJOI2004]Swamp 沼泽鳄鱼

2014.12.19 13:05 Fri| 0 visits oi_2015| 2015_刷题日常| Text

Solution

为什么题目中的鳄鱼变成了食人鱼 0.0

若没有食人鱼的限制,则这又是一道水到爆的矩阵乘法,而由于食人鱼的周期只有三种可能,取其最小公倍数12为周期。对于第i个时刻,若有食人鱼在j石墩处,则将在第i-1个时刻通向j的边和第i个时刻从j出发的边设为0。这样建立12个矩阵,便可进行转移。

Code

#include <bits/stdc++.h>
using namespace std;
#define N 55
#define mod 10000

struct matrix
{
    int n,m[N][N];
    matrix(int _n=0):n(_n)
    {
        memset(m,0,sizeof m);
    }
    friend matrix operator *(const matrix &a,const matrix &b)
    {
        matrix re(a.n);
        for(int i=0;i<re.n;i++)
            for(int j=0;j<re.n;j++)
                for(int k=0;k<re.n;k++)
                    re.m[i][j]=(re.m[i][j]+a.m[i][k]*b.m[k][j])%mod;
        return re;
    }
    friend matrix pow(matrix m,int t)
    {
        matrix re(m.n);
        for(int i=0;i<m.n;i++)
            re.m[i][i]=1;
        while(t)
        {
            if(t&1) re*=m;
            m*=m; t>>=1;
        }
        return re;
    }
    matrix &operator *=(const matrix &x){ return *this=*this*x; }
    void print()
    {
        for(int i=0;i<n;i++,puts(""))
            for(int j=0;j<n;j++)
                cout<<m[i][j]<<' ';
    }
};

inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

matrix a[13];
int n,m,start,end,k,nfish;

int main()
{
    cin>>n>>m>>start>>end>>k;
    matrix p(n);
    for(int x,y,i=1;i<=m;i++)
        x=read(), y=read(), p.m[x][y]=p.m[y][x]=1;
    for(int i=1;i<=12;i++) a[i]=p;
    cin>>nfish;
    for(int t,i=1;i<=nfish?t=read(),1:0;i++)
        for(int x,j=1;j<=t?x=read(),1:0;j++)
            for(int k=1;k<=12;k++)
                if(k%t==j%t)
                    for(int l=0;l<n;l++)
                        a[k-1].m[l][x]=a[k].m[x][l]=0;
    a[0]=a[1];
    for(int i=2;i<=12;i++)
        a[0]*=a[i];
    a[0]=pow(a[0],k/12);
    for(int i=1;i<=k%12;i++)
        a[0]*=a[i];
    cout<<a[0].m[start][end]<<endl;

}