神仙的博客(还没看)

题目

ZJOI2005沼泽鳄鱼

就按照12为一个周期，然后转移的时候记得吧一些列删掉

#include<bits/stdc++.h>
using namespace std;
const int mod=10000;
const int N=60;
int n,m,S,T,K;
int nf,used[N][12];
int p[N];
struct mat
{
    int a[N][N];
    mat(){memset(a,0,sizeof(a));}
    void init()
    {
        for(int i=1;i<=n;i++) a[i][i]=1;
        return;
    }
    mat operator *(const mat &b)  
    {
        mat c;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                for(int k=1;k<=n;k++)
                {
                    c.a[i][j]+=a[i][k]*b.a[k][j]%mod;
                    c.a[i][j]%=mod;
                }
            }
        }
        return c;
    }
}st,e,w[15],al;
void out(mat &x)
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            printf("%d ",x.a[i][j]);
        }
        printf("\n");
    }
    printf("\n");
    return;
}
mat qpow(mat a,int b)
{
    mat res;
    res.init();
    for(;b>0;b/=2,a=a*a) if(b%2) res=res*a;
    return res;
}
int main()
{
    scanf("%d%d%d%d%d",&n,&m,&S,&T,&K);
    S++,T++;
    int u,v;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&u,&v);
        u++,v++;
        e.a[u][v]=1;
        e.a[v][u]=1;
    }
    st.a[1][S]=1;
    int q;
    scanf("%d",&nf);
    for(int i=1;i<=nf;i++)
    {
        scanf("%d",&q);
        for(int j=0;j<q;j++) scanf("%d",&p[j]),p[j]++;
        for(int j=0;j<12;j++) used[p[j%q]][j]=1; 
    }
    for(int i=1;i<=12;i++)
    {
        w[i]=e;
        for(int j=1;j<=n;j++)
        {
            if(!used[j][i%12]) continue;
            for(int k=1;k<=n;k++) w[i].a[k][j]=0;
        }
    }
    al.init();
    for(int i=1;i<=12;i++) al=al*w[i];
    st=st*qpow(al,K/12);
    for(int i=1;i<=K%12;i++) st=st*w[i];
    printf("%d\n",st.a[1][T]);
    return 0;
}