P1373 小a和uim之大逃离

218 阅读2分钟

题目链接

小a和uim之大逃离

思路

DP题。
题目中说瓶子中装了k+1的魔液时会清零,也就是mod\ (k+1)。为计算方便,输入k时直接++k

设状态。

最初的思想是令f[i][j][p][q][0/1]表示两人在矩阵的(i,j)处,手中分别有p,q点魔液,0/1表示当前位置轮到哪一个人(假设0代表小a,1代表uim)吸收魔液。但是这样做炸空间。

注意到一个方案合法时只需要二者手中魔液相同即可,并不需要考虑各自魔液分别为多少。所以把p,q缩为一维c,记录二者(即小a的魔液-uim的魔液)手中魔液的差值。

因为起点终点任意,所以方法总数为:

\sum_{i=1}^n \sum_{j=1}^mf[i][j][0][1]

状态转移方程

依题意只能向下和向右走。有以下四个转移方程(k已自加1):

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][1]+=f[i-1][j][(c+a[i][j])\%k][0]\\
f[i][j][c][1]+=f[i][j-1][(c+a[i][j])\%k][0]

每次要记得\%P

有一个细节,拿第一个方程举例,现在要更新0(也就是小a)取魔液的状态,那么取完之后c必定变大,所以之前状态对应的c^,一定是由c减去a[i][j]得来,因此两组方程的[0/1]不可以互换。

注意边界条件
对于每一个点都可以作为起点,由0(即小a)取魔液。所以f[i][j][a[x][y]][0]都初始化为1

对于(c+a[i][j])\%k很好理解,c-a[i][j]+k推导过程如下:
已知c,要推出上一个状态的c^,
现有等式:

c=(c^,+a[i][j])\%k

因为

c^,< k,a[i][j]< k

所以有

c^,+a[i][j]< 2k

k+c=c^,+a[i][j]\ \ (c<a[i][j])

c^,=k+c-a[i][j]

证毕。

代码

#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;
}