思路

这道题是一道比较典型的dp求方案数。这是我第一次做dp方案数的题目，这篇题解就作为我dp方案数专题的第一篇文章吧。

首先思考本题的dp方程时，需要用方案数dp的方式去思考。方案数是叠加的，所以每次转移时的运算就是相加而不是取最大最小值。这样的话，我们可以来真正的来思考本题方程。首先方程中需要有点的位置，亦需要小a和uim的状态。我们如何把魔液这个元素考虑进来呢？我们增加一个维度，来记录俩人魔液罐子的差值（当然，为负数的时候我们就可以加一个k进行取模运算，保证在正数范围内可以访问）。所以，dp[i][j][h][0/1]可以表示为走到(i,j)时两人魔罐插值为h时的方案数量，其中0代表小a走，1代表uim走。所以方程如下：

F[i][j][h][0] = (F[i][j][h][0] + F[i – 1][j][(h – map[i][j] + k) % k][1]) % P;
F[i][j][h][0] = (F[i][j][h][0] + F[i][j – 1][(h – map[i][j] + k) % k][1]) % P;
F[i][j][h][1] = (F[i][j][h][1] + F[i – 1][j][(h + map[i][j]) % k][0]) % P;
F[i][j][h][1] = (F[i][j][h][1] + F[i][j – 1][(h + map[i][j]) % k][0]) % P;

代码如下：

// P1373.cpp
#include <iostream>

using namespace std;
// Variables;
const int maxn = 802;
const int INF = 0x7fffffff;
const int P = 1000000007;
int n, m, k;
int map[maxn][maxn];
int F[maxn][maxn][20][2];
// Start to dp;
void dp()
{
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            for (int h = 0; h <= k; h++)
            {
                F[i][j][h][0] = (F[i][j][h][0] + F[i - 1][j][(h - map[i][j] + k) % k][1]) % P;
                F[i][j][h][0] = (F[i][j][h][0] + F[i][j - 1][(h - map[i][j] + k) % k][1]) % P;
                F[i][j][h][1] = (F[i][j][h][1] + F[i - 1][j][(h + map[i][j]) % k][0]) % P;
                F[i][j][h][1] = (F[i][j][h][1] + F[i][j - 1][(h + map[i][j]) % k][0]) % P;
            }
}

int main()
{
    // Input;
    cin >> n >> m >> k, ++k;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            // Initialize;
            cin >> map[i][j], F[i][j][map[i][j]][0] = 1;
    dp();
    long long ans = 0;
    // Calculate the answer;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            ans += F[i][j][0][1], ans %= P;
    // Output;
    cout << ans;
    return 0;
}