题解 P1373 【小a和uim之大逃离】

题目

奇怪的递推（DP），居然没有自己做出来QAQ

---

初始思路

用f[i][j][x][y]表示取到 点\(i,j\)时，小a有\(x\)魔液，uim有\(y\)魔液，的方案数

显然MLE，且复杂度不优秀，\(O(nmk^2)\)

优化表示方式

答案要求两人差为零的方案数，所以只考虑两者魔液之差

用f[i][j][x][p]表示表示取到 点\(i,j\)时，两人之差为\(x\)，由\(p\)（小a或uim）取最后一堆的方案数

转移方程

// 小a
f[i][j][x][0] += f[i-1][j][x-a[i][j]][1]// 上边
f[i][j][x][0] += f[i][j-1][x-a[i][j]][1]// 左边
// uim
f[i][j][x][1] += f[i-1][j][x+a[i][j]][0]
f[i][j][x][1] += f[i][j-1][x+a[i][j]][0]

细节

注意模的是k+1，所以我一开始k++

因为只能由小a取第一堆，初始值：

f[i][j][a[i][j]][0] = 1

只能由uim取最后一堆，答案为：

ans += f[i][j][0][1]

空间开到f[805][805][20][2]左右，不然容易MLE

完整代码

#include <cstdio>
#include <cctype>

using namespace std;

namespace BANANA {

template<typename T> inline void read(T &x) {
    x = 0; T k = 1; char in = getchar();
    while (!isdigit(in)) { if (in == '-') k = -1; in = getchar(); }
    while (isdigit(in)) x = x * 10 + in - '0', in = getchar();
    x *= k;
}

typedef long long ll;

const int MOD = 1e9 + 7;
const int N = 805;

int n, m, k;
ll ans;
int a[N][N], f[N][N][20][2];

inline int mod(int x) {
    return (x + k) % k;
}

inline void main() {
    read(n), read(m), read(k);
    k++;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j) {
            read(a[i][j]), a[i][j] %= k;
            f[i][j][a[i][j]][0] = 1;
        }
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            for (int x = 0; x < k; ++x) {
                f[i][j][x][0] = (f[i][j][x][0] + f[i-1][j][mod(x-a[i][j])][1] + f[i][j-1][mod(x-a[i][j])][1]) % MOD;
                f[i][j][x][1] = (f[i][j][x][1] + f[i-1][j][mod(x+a[i][j])][0] + f[i][j-1][mod(x+a[i][j])][0]) % MOD;
            }
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            (ans += f[i][j][0][1]) %= MOD;
    printf("%lld\n", ans);
}
}

int main() {
    BANANA::main();
    return 0;
}