BZOJ 1898 沼泽鳄鱼(矩阵快速幂)

时间：2021-09-24 00:52:46
没有食人鱼不是裸题吗，用一个向量表示从s到1..N的距离，然后不停乘邻接矩阵行了，当然快速幂
有食人鱼，发现食人鱼最多十二个邻接矩阵一循环，处理出12个作为1个然后快速幂行了
 
怎么处理呢？
假设食人鱼在j时刻到达x这个点，那么j时刻的邻接矩阵x这一列全是0，因为他要求下一个矩阵的贡献上不能有x这一列贡献的。
 
#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

using namespace std;

const int N=,MOD=1e4;

typedef long long ll;

inline int read(){

    char c=getchar();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

    return x*f;

}

int n,m,s,t,k,x,y,fish,f[];

struct Mat{

    int a[N][N];

    Mat(){memset(a,,sizeof(a));}

    void ini(){for(int i=;i<=n;i++) a[i][i]=;}

}g[],ans;

inline Mat operator *(Mat A,Mat B){

    Mat C;

    for(int k=;k<=n;k++)

        for(int i=;i<=n;i++) if(A.a[i][k])

            for(int j=;j<=n;j++) if(B.a[k][j])

                C.a[i][j]=(C.a[i][j]+A.a[i][k]*B.a[k][j])%MOD;

    return C;

}

inline Mat operator ^(Mat A,int k){

    Mat ans;ans.ini();

    for(;k;k>>=,A=A*A)

        if(k&) ans=ans*A;

    return ans;

}

void print(Mat A){

    puts("hiMat");

    for(int i=;i<=n;i++){

        for(int j=;j<=n;j++) printf("%d ",A.a[i][j]);

        puts("");

    }

}

int main(){

    //freopen("in.txt","r",stdin);

    n=read();m=read();s=read()+;t=read()+;k=read();

    for(int i=;i<=m;i++){

        x=read()+;y=read()+;

        for(int j=;j<=;j++) g[j].a[x][y]=g[j].a[y][x]=;

    }

    fish=read();

    for(int i=;i<=fish;i++){

        int T=read();

        for(int j=;j<=T;j++) f[j]=read()+;

        for(int j=;j<=;j++)

            for(int k=;k<=n;k++) g[j].a[k][f[j%T+]]=;

    }

    g[].ini();

    for(int i=;i<=;i++) g[]=g[]*g[i];

    ans=g[]^(k/);

    for (int i=;i<=k%;i++) ans=ans*g[i];

    printf("%d",ans.a[s][t]);

}

相关文章