【BZOJ1898】[ZJOI2005]沼泽鳄鱼（矩阵快速幂，动态规划）

题面

题解

先吐槽，说好了的鳄鱼呢，题面里面全是食人鱼

看到数据范围一眼想到矩乘。

先不考虑食人鱼的问题，直接设\(f[i][j]\)表示\(j\)时刻到达了\(i\)号节点的方案数，转移显然。

接下来考虑食人鱼的影响，显然是在模\(2,3,4\)的意义下，某个特定余数时刻某个点不能到达，而\(lcm(2,3,4)=12\)，所以显然以\(12\)为周期，构建\(12\)个矩阵，每次一起乘就好了。多出来的部分再手动乘一下就没有问题了。

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

#define MAX 55

#define MOD 10000

inline int read()

{

	int x=0;bool t=false;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=true,ch=getchar();

	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

	return t?-x:x;

}

int n,m,St,Ed,K,a[MAX];

struct Matrix

{

	int s[MAX][MAX];

	void clear(){memset(s,0,sizeof(s));}

	void init(){clear();for(int i=1;i<=n;++i)s[i][i]=1;}

	int*operator[](int x){return s[x];}

}T[15],S,g;

Matrix operator*(Matrix a,Matrix b)

{

	Matrix ret;ret.clear();

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

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

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

				ret[i][j]=(ret[i][j]+a[i][k]*b[k][j])%MOD;

	return ret;

}

Matrix fpow(Matrix a,int b)

{

	Matrix s;s.init();

	while(b){if(b&1)s=s*a;a=a*a;b>>=1;}

	return s;

}

int main()

{

	n=read();m=read();St=read()+1;Ed=read()+1;K=read();

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

	{

		int u=read()+1,v=read()+1;

		g[u][v]=g[v][u]=1;

	}

	for(int i=1;i<=12;++i)T[i]=g;

	int nf=read();

	while(nf--)

	{

		int t=read();

		for(int i=0;i<t;++i)a[i]=read()+1;

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

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

				T[i][j][a[i%t]]=0;

	}

	S.init();for(int i=1;i<=12;++i)S=S*T[i];

	S=fpow(S,K/12);

	for(int i=1;i<=K%12;++i)S=S*T[i];

	printf("%d\n",S[St][Ed]);

	return 0;

}

巴特西

【BZOJ1898】[ZJOI2005]沼泽鳄鱼（矩阵快速幂，动态规划）

【BZOJ1898】[ZJOI2005]沼泽鳄鱼（矩阵快速幂，动态规划）

题面

题解

最新文章

热门文章