description:

瞬间,地面上出现了一个n*m的巨幅矩阵,矩阵的每个格子上有一坨0~k不等量的魔液。怪物各给了小a和uim一个魔瓶,说道,你们可以从矩阵的任一个格子开始,每次向右或向下走一步,从任一个格子结束。开始时小a用魔瓶吸收地面上的魔液,下一步由uim吸收,如此交替下去,并且要求最后一步必须由uim吸收。魔瓶只有k的容量,也就是说,如果装了k+1那么魔瓶会被清空成零,如果装了k+2就只剩下1,依次类推。怪物还说道,最后谁的魔瓶装的魔液多,谁就能活下来。小a和uim感情深厚,情同手足,怎能忍心让小伙伴离自己而去呢?沉默片刻,小a灵机一动,如果他俩的魔瓶中魔液一样多,不就都能活下来了吗?小a和他的小伙伴都笑呆了!

现在他想知道他们都能活下来有多少种方法。

  • 100 % n , m < = 800 , 1 < = k < = 15 对于100\%的数据,n,m<=800,1<=k<=15 100%n,m<=800,1<=k<=15

这题目描述的格式也是可以

solution:

  • 简单的dp。

  • f [ i ] [ j ] [ p ] [ 0 / 1 ] f[i][j][p][0/1] f[i][j][p][0/1]表示在位置 ( i , j ) (i,j) (i,j),小a与uim的权值相差p,0表示这一步是小a走的,1表示uim。

  • 显然两人的权值都要%k,但是发现其实按照题意是%(k+1)

  • f [ i ] [ j ] [ p ] [ 0 ] + = f [ i 1 ] [ j ] [ ( p a [ i ] [ j ] + k ) % k ] [ 1 ] ( i 1 > = 1 ) f[i][j][p][0]+=f[i-1][j][(p-a[i][j]+k)\%k][1] (i-1>=1) f[i][j][p][0]+=f[i1][j][(pa[i][j]+k)%k][1](i1>=1)

  • f [ i ] [ j ] [ p ] [ 0 ] + = f [ i ] [ j 1 ] [ ( p a [ i ] [ j ] + k ) % k ] [ 1 ] ( j 1 > = 1 ) f[i][j][p][0]+=f[i][j-1][(p-a[i][j]+k)\%k][1] (j-1>=1) f[i][j][p][0]+=f[i][j1][(pa[i][j]+k)%k][1](j1>=1)

  • f [ i ] [ j ] [ p ] [ 1 ] + = f [ i 1 ] [ j ] [ ( p + a [ i ] [ j ] ) % k ] [ 0 ] ( i 1 > = 1 ) f[i][j][p][1]+=f[i-1][j][(p+a[i][j])\%k][0] (i-1>=1) f[i][j][p][1]+=f[i1][j][(p+a[i][j])%k][0](i1>=1)

  • f [ i ] [ j ] [ p ] [ 1 ] + = f [ i ] [ j 1 ] [ ( p + a [ i ] [ j ] ) % k ] [ 0 ] ( j 1 > = 1 ) f[i][j][p][1]+=f[i][j-1][(p+a[i][j])\%k][0] (j-1>=1) f[i][j][p][1]+=f[i][j1][(p+a[i][j])%k][0](j1>=1)

  • 以上是四种状态转移方程(别忘了每个都要%1e7),还要判断不能从矩阵外面走过来(>1)

  • 最后的答案即为将所有 f [ i ] [ j ] [ 0 ] [ 1 ] f[i][j][0][1] f[i][j][0][1]累加起来(两人相差为0,uim获取最后一个)

code:

#include<cstdio>
#define mod 1000000007
using namespace std;
int a[805][805];
int f[805][805][20][2];
int main()
{
	int n,m,k;
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			scanf("%d",&a[i][j]);
			f[i][j][a[i][j]][0]=1;
		}
	}
	k++;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			for(int p=0;p<k;p++)
			{
				if(i>=2)
				{
					f[i][j][p][1]+=f[i-1][j][(p+a[i][j])%k][0];
					f[i][j][p][1]%=mod;
					f[i][j][p][0]+=f[i-1][j][(p-a[i][j]+k)%k][1];
					f[i][j][p][0]%=mod;
				}
				if(j>=2)
				{
					f[i][j][p][1]+=f[i][j-1][(p+a[i][j])%k][0];
					f[i][j][p][1]%=mod;
					f[i][j][p][0]+=f[i][j-1][(p-a[i][j]+k)%k][1];
					f[i][j][p][0]%=mod;
				}
			}
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			ans=(ans+f[i][j][0][1])%mod;
		}
	}
	printf("%d\n",ans);
	return 0;
}