BruceJay's Blog

BZOJ1898 沼泽鳄鱼

| Comments

To start with

Bruce的模拟考试题,然而Bruce并没有做出来。

Problem

Solution

听同机房同学说:一眼矩阵乘法。
因为食人鱼的活动周期只可能是2,3,4,即所有食人鱼的活动周期的最小公倍数至多为12。
于是f[i][u][v]表示从u走i步到v的方案数,只用求i=1~12的就行了。
对于k,将k分成12x+y,x那一部分矩乘解决,剩下的就用f数组了。

Code

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 50;
const int R = 15;
const int Mod = 1e4;
struct Matrix{int v[N][N];}a,ans;
int f[R][N][N]; bool Bridge[N][N];
bool attacked[R][N]; int p[4];
int n,m,s,t,k,nfish,tot=0;

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

Matrix Mul(Matrix x,Matrix y)
{
    Matrix res;
    memset(res.v,0,sizeof(res.v));
    for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
    for(int l=0;l<n;l++){
        res.v[i][j]+=x.v[i][l]*y.v[l][j];
        res.v[i][j]%=Mod;
    }
    return res;
}

Matrix PowerMod(Matrix x,int y)
{
    Matrix res;
    memset(res.v,0,sizeof(res.v));
    for(int i=0;i<n;i++) res.v[i][i]=1;
    for(int i=y;i;i>>=1,x=Mul(x,x))
        if(i&1) res=Mul(res,x);
    return res;
}

void DP(int x)
{
    if(!attacked[0][x]) f[0][x][x]=1;
    for(int i=1;i<=12;i++){
        for(int u=0;u<n;u++)
        for(int v=0;v<n;v++)
            if(Bridge[u][v]){
                f[i][x][u]+=f[i-1][x][v];
                f[i][x][u]%=Mod;
                f[i][x][v]+=f[i-1][x][u];
                f[i][x][v]%=Mod;
            }
        for(int u=0;u<n;u++)
            if(attacked[i][u]) f[i][x][u]=0;
    }
    for(int i=0;i<n;i++) a.v[x][i]=f[12][x][i];
}

int main()
{
    int u,v,T;
    freopen("swamp.in","r",stdin);
    freopen("swamp.out","w",stdout);
    n=read(); m=read();
    s=read(); t=read(); k=read();
    for(int i=0;i<m;i++){
        u=read(); v=read();
        Bridge[u][v]=true;
    }
    nfish=read();
    for(int i=0;i<nfish;i++){
        T=read();
        for(int j=0;j<T;j++) p[j]=read();
        for(int j=0;j<=12;j++)
            attacked[j][p[j%T]]=true;
    }
    memset(a.v,0,sizeof(a.v));
    for(int i=0;i<n;i++) DP(i);
    ans=PowerMod(a,k/12);
    for(int i=0;i<n;i++) tot=(tot+ans.v[s][i]*f[k%12][i][t])%Mod;
    printf("%d",tot);
    return 0;
}

Last but not least

比较老的ZJOI的题。Bruce考场上没做出来。

Comments

comments powered by Disqus