bzoj 1898: [Zjoi2005]Swamp 沼泽鳄鱼【dp+矩阵快速幂】

注意到周期234的lcm只有12，也就是以12为周期，可以走的状态是一样的

所以先预处理出这12个状态的转移矩阵，乘起来，然后矩阵快速幂优化转移k/12次，然后剩下的次数暴力转移即可

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

const int mod=10000;

int n,m,s,t,k,x,y,nf,T,w[60];

struct jz

{

    int a[60][60];

    jz operator * (jz y)

    {

        jz c;

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

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

			{

				c.a[i][j]=0;

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

					c.a[i][j]=(c.a[i][j]+a[i][k]*y.a[k][j])%mod;

			}

        return c;

    }

}a,b[15],ans;

int main()

{

    scanf("%d%d%d%d%d",&n,&m,&s,&t,&k);

    s++;t++;

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

    {

        scanf("%d%d",&x,&y);

        x++;y++;

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

			b[j].a[x][y]=b[j].a[y][x]=1;

    }

    scanf("%d",&nf);

    for(int i=1;i<=nf;i++)

    {

        scanf("%d",&T);

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

			scanf("%d",&w[j]),w[j]++;

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

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

				b[j].a[k][w[j%T+1]]=0;

    }

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

		a.a[i][i]=1,ans.a[i][i]=1;

    for(int i=1;i<=12;i++)

		a=a*b[i];

    int kk=k/12;

    while(kk)

    {

        if(kk&1)

			ans=ans*a;

        a=a*a;

        kk>>=1;

    }

    for(int i=1;i<=k%12;i++)

		ans=ans*b[i];

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

    return 0;

}

巴特西

bzoj 1898: [Zjoi2005]Swamp 沼泽鳄鱼【dp+矩阵快速幂】

最新文章

热门文章