bzoj1898: [Zjoi2005]Swamp 沼泽鳄鱼

传送门
首先我们发现lcm(2,3,4)=12很小
于是我们预处理出12个时刻内所有合法转移
然后我们大力矩阵乘法就可以了。

#include<cstring>
#include<cmath>   
#include<cstdio>  
#include<iostream>  
#include<cstdlib>   
#include<algorithm>
#define ll long long
#define N 50005
using namespace std;
struct edge{int x,y,z;}e[3005];
int n,m,s,t,k,p,fish[25][10];
struct matrix{
    int a[55][55];
    void clear(){memset(a,0,sizeof(a));}
    matrix operator * (const matrix b) const
    {
        matrix c;
        c.clear();
        for (int i=0;i<n;i++)
            for (int j=0;j<n;j++)
                for (int k=0;k<n;k++)
                    c.a[i][j]=(a[i][k]*b.a[k][j]+c.a[i][j])%10000;
        return c;
    }
    void build(int tim){
        clear();
        int ok[55];
        memset(ok,1,sizeof(ok)); 
        for (int i=1;i<=p;i++) ok[fish[i][tim%fish[i][4]]]=0;
        for (int i=1;i<=m;i++){
            if (ok[e[i].x]) a[e[i].y][e[i].x]=1; 
            if (ok[e[i].y]) a[e[i].x][e[i].y]=1;
        }
    }
    matrix pow(int x){
        matrix c,d;
        c.clear();
        memcpy(d.a,a,sizeof(a));
        for (int i=0;i<n;i++) c.a[i][i]=1;
        while (x){
            if (x%2) c=c*d;
            d=d*d;
            x/=2;
        }
        return c;
    }
}ans,ppp[15]; 
int main(){
    scanf("%d%d%d%d%d",&n,&m,&s,&t,&k);
    for (int i=1;i<=m;i++) scanf("%d%d",&e[i].x,&e[i].y);
    scanf("%d",&p);
    for (int i=1;i<=p;i++){
        scanf("%d",&fish[i][4]);
        for (int j=0;j<fish[i][4];j++) scanf("%d",&fish[i][j]);
    }
    for (int i=1;i<=12;i++) ppp[i].build(i);
    for (int i=0;i<n;i++) ppp[0].a[i][i]=1;
    for (int i=1;i<=12;i++) ppp[i]=ppp[i-1]*ppp[i];
    ans=ppp[12].pow(k/12)*ppp[k%12];
    printf("%d",ans.a[s][t]);
}