题目链接
思路
DP题。
题目中说瓶子中装了的魔液时会清零,也就是。为计算方便,输入时直接。
设状态。
最初的思想是令表示两人在矩阵的处,手中分别有点魔液,表示当前位置轮到哪一个人(假设代表小a,代表uim)吸收魔液。但是这样做炸空间。
注意到一个方案合法时只需要二者手中魔液相同即可,并不需要考虑各自魔液分别为多少。所以把缩为一维,记录二者(即小a的魔液-uim的魔液)手中魔液的差值。
因为起点终点任意,所以方法总数为:
状态转移方程
依题意只能向下和向右走。有以下四个转移方程(已自加):
每次要记得。
有一个细节,拿第一个方程举例,现在要更新0(也就是小a)取魔液的状态,那么取完之后必定变大,所以之前状态对应的一定是由减去得来,因此两组方程的不可以互换。
注意边界条件
对于每一个点都可以作为起点,由0(即小a)取魔液。所以都初始化为。
对于很好理解,推导过程如下:
已知,要推出上一个状态的。
现有等式:
因为
所以有
即
得
证毕。
代码
#include<bits/stdc++.h>
#define rep(i,st,ed) for(int i=st;i<=ed;++i)
using namespace std;
const int N=802,P=1E9+7;
int n,m,k;
long long ans;
int a[N][N],f[N][N][18][2];
int main()
{
cin>>n>>m>>k;
++k;
rep(i,1,n)
{
rep(j,1,m)
{
cin>>a[i][j];
a[i][j]%=k;
f[i][j][a[i][j]][0]=1;
}
}
rep(i,1,n)
{
rep(j,1,m)
{
rep(c,0,k)
{
f[i][j][c][0]+=f[i-1][j][(c-a[i][j]+k)%k][1];
f[i][j][c][0]+=f[i][j-1][(c-a[i][j]+k)%k][1];
f[i][j][c][0]%=P;
f[i][j][c][1]+=f[i-1][j][(c+a[i][j]+k)%k][0];
f[i][j][c][1]+=f[i][j-1][(c+a[i][j]+k)%k][0];
f[i][j][c][1]%=P;
}
}
}
rep(i,1,n)
{
rep(j,1,m)
{
ans=(ans+f[i][j][0][1])%P;
}
}
cout<<ans<<endl;
}