https://www.luogu.org/problemnew/show/P1373

设f(l,i,j):以(i,j)为左上角(起点)，小a比小uim多l的方案数

理解：假如在一个点(i,j)小a吸收了x，小uim在他相邻位置吸收了y，即小a比小uim多吸收x-y，则(i,j)为起点最后小a小uim相等的方案数转化为：以小uim再走一步的位置为起点，并且最后小a比小uim多吸收y-x的方案数(全都在模k下)。

状态转移方程见代码解释。

求的是方案数，状态不合法方案数为0就行了，不需要设置-1。

注意一开始k++，在模k下。

#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007
int n,m,k,a[1000][1000],f[20][1000][1000],ans;

int main()
{
//	freopen("input.in","r",stdin);
	int num;
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>a[i][j];
	k++;
	for(int i=n;i>=1;i--)
	{
		for(int j=m;j>=1;j--)
		{
			for(int l=0;l<k;l++)
			{
				if(j!=m)   //最右一列不能继续向右 
				{
					num=(a[i][j]-a[i][j+1]+k)%k;   //起点比右点多了num 
					f[l][i][j]=(f[(k+(l-num))%k][i][j+2]+f[(k+(l-num))%k][i+1][j+1])%mod;//小uim再走一步 
					if(num==l)f[l][i][j]++;   //这两个点可以单独形成一个组合 
				}
				if(i!=n)   //最下一行不能继续向下 
				{
					num=(a[i][j]-a[i+1][j]+k)%k;    //起点比下点多了num
					f[l][i][j]+=(f[(k+(l-num))%k][i+2][j]+f[(k+(l-num))%k][i+1][j+1])%mod;//小uim再走一步 
					if(num==l)f[l][i][j]++;   //这两个点可以单独形成一个组合
					f[l][i][j]%=mod;
				}
			}
		}
	}
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)ans=(ans+f[0][i][j])%mod;
	cout<<ans<<endl;
	//for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)printf("f[0][%d][%d]=%d\n",i,j,f[0][i][j]);
	return 0;
}