小a和uim之大逃离

题目描述

小a和uim来到雨林中探险。突然前方出现了一个披头散发、青面獠牙的怪物,低沉着声音说:“呵呵,既然你们来到这,只能活下来一个!”。

瞬间,地面上出现了一个$n \times m$的巨幅矩阵,矩阵的每个格子上有一坨$0 - k$不等量的魔液。怪物各给了小a和uim一个魔瓶,说道,你们可以从矩阵的任一个格子开始,每次向右或向下走一步,从任一个格子结束。开始时小a用魔瓶吸收地面上的魔液,下一步由uim吸收,如此交替下去,并且要求最后一步必须由uim吸收。魔瓶只有$k$的容量,也就是说,如果装了$k+1$那么魔瓶会被清空成零,如果装了$k+2$就只剩下$1$,依次类推。怪物还说道,最后谁的魔瓶装的魔液多,谁就能活下来。

沉默片刻,小a灵机一动,如果他俩的魔瓶中魔液一样多,不就都能活下来了吗?

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

输入 $n,m,k$, 接下来是$n * m$的矩阵,表示矩阵每一个点的魔液量

答案对$1e9 + 7$取模

$n,m\le 800,1\le k\le 15$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
//做这道题的时候真的蠢死了..
//总之要记住保存差值的这种套路就好

const int mod = (1e9) + 7;
int sov[810][810][20][2];
//之前这里数组开的不够大然后WA了一波
//sov[i][j][u][k]表示走到(i,j)并且小a的魔瓶与小uim的魔瓶差了u点魔液,并且当前格由k取的方案数
//0:小a,1:小uim

int main(){
n = read(), m = read(), k = read();
++ k;
//这个魔瓶很奇妙地不会在装满的时候清空,而是在溢出的时候,所以我们要把魔瓶的模数改成k+1
for(int i = 1; i <= n; ++ i){
for(int j = 1; j <= m; ++ j){//枚举,令路径在(i,j)结束
now = read();
sov[i][j][now % k][0] = 1;//①
//从这个点开始取是算作一种情况的
for(int d = 0, u; d <= k; ++ d){//枚举所有可能的差值
u = (d + now)%k;
//从①可以看出,这里是用小a来减小uim
//也就是说,小uim取完魔液之后差值会减小(在%k前)
//所以如果当前点由小uim取后差值为u,那么之前的差值就必须是(d + now)%k才行
sov[i][j][d][1] = (sov[i][j-1][u][0] + sov[i-1][j][u][0]) % mod;
u = (d - now + k)%k;
//这里是同理的
//小a取完魔液后差值会增加,所以之前是(d - now)
//然后负数模出来会是负数
//比如(-7)%10=-7
//并不很懂它的计算机制
//总之还要加上一个k保证其为正就对了
sov[i][j][d][0] = (sov[i][j-1][u][1] + sov[i-1][j][u][1]) % mod;
}
ans = (ans + sov[i][j][0][1])%mod;//加上差值为0并由小uim取了(i,j)的情况
}
}
printf("%lld", ans);
//题解说如果在过程中开LL会MLE
//最多只能在统计ans时小心翼翼的开成LL
//真是毒瘤题(?)
//不过似乎可以用滚动数组的技巧啊
//实在懒得写了就这样吧
return 0;
}