【[SCOI2009]迷路】

时间：2024-11-25 22:36:14

大水题一遍

过掉比较繁琐的拆点还是非常开心的

发现每一条边的边权可能不是\(1\)，但是边权的范围非常小，同时点数也非常小，只有\(n<=10\)，所以我们可以将一个点拆成九个点，之后随便一连边就跑过去了

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#define re register

#define maxn 105

#define LL long long

const int mod=2009;

int a[maxn][maxn],ans[maxn][maxn];

int sz;

inline void did_a()

{

	int mid[maxn][maxn];

	for(re int i=1;i<=sz;i++)

		for(re int j=1;j<=sz;j++)

			mid[i][j]=a[i][j],a[i][j]=0;

	for(re int k=1;k<=sz;k++)

		for(re int i=1;i<=sz;i++)

			for(re int j=1;j<=sz;j++)

				a[i][j]=(a[i][j]+mid[i][k]*mid[k][j])%mod;

}

inline void did_ans()

{

	int mid[maxn][maxn];

	for(re int i=1;i<=sz;i++)

		for(re int j=1;j<=sz;j++)

			mid[i][j]=ans[i][j],ans[i][j]=0;

	for(re int k=1;k<=sz;k++)

		for(re int i=1;i<=sz;i++)

			for(re int j=1;j<=sz;j++)

				ans[i][j]=(ans[i][j]+mid[i][k]*a[k][j])%mod;

}

inline void quick(LL b)

{

	while(b)

	{

		if(b&1ll) did_ans();

		b>>=1ll;

		did_a();

	}

}

inline int read()

{

	char c=getchar();

	int x=0;

	while(c<'0'||c>'9') c=getchar();

	while(c>='0'&&c<='9')

		x=(x<<3)+(x<<1)+c-48,c=getchar();

	return x;

}

int n;

LL m;

char S[maxn];

int main()

{

	n=read(),m=read();

	sz=n*10;

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

	{

		int now=(i-1)*10;

		for(re int j=2;j<=9;j++)

			a[j+now-1][j+now]=1;

	}

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

	{

		scanf("%s",S+1);

		int now=(i-1)*10;

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

		{

			if(S[j]=='0') continue;

			int to=S[j]-48;

			a[now+9][(j-1)*10+10-to]=1;

		}

	}

	for(re int i=1;i<=sz;i++)

		ans[i][i]=1;

	quick(m);

	printf("%d\n",ans[9][(n-1)*10+9]);

	return 0;

}

相关文章