二维dp+背包

前面的碎碎念

不得不说，这次的小白月赛的题目真的是很好，有的题目让人耳目一新，有的题目让人思维拓展，更有的题目昨晚直呼太爽了，而这个题目真的很让人耳目一新，没想到还可以这么做。

题目描述
有一个n×m的网格地图，每个点有个值
​
，现在牛牛要从（1，1）走到（n，m），他可以往右边或者往下走，每次到一个点会获得当前的点权值，并将权值和mod 1e4+7，当牛牛从不同方式走到（n，m）的时候能获得多少种权值和？

题目分析：题目要求的是一共有多少个数字可以由a数组构成，那么我们便可以枚举mod范围内所有的数字的情况，看看a数组的元素能不能组成这个数，因为题目是二维dp问题，每次可以往下和往右移动一次，那么我们便增加一维用于记录mod范围内的数字，然后依次枚举，我们维护一个状态，每次从上和左边移动下来，但是这个题目还要注意一个地方，那就是相减可能会出现负数，（因为我们前面模了一下）所以我们要在计算的时候，加一个mod并且对减去后的数字模一下，这样就能防止溢出（防止出现负数），最后我们在枚举每个数字，如果这个数字能被a数组组成，那么三维dp里面的数就不为0.

#include <bits/stdc++.h>
using namespace std;
const int mod = 1e4 + 7;
int a[1010][1010];
bool dp[110][110][10010];
int main()
{
    int n, m;
    int ans = 0;
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
        {
            scanf("%d", &a[i][j]);
            a[i][j] %= mod;
        }
    dp[1][1][a[1][1]] = 1;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            for (int k = mod - 1; k >= 0; --k)
            {
                dp[i][j][k] += dp[i - 1][j][(k - a[i][j] + mod) % mod];
                dp[i][j][k] += dp[i][j - 1][(k - a[i][j] + mod) % mod];
            }
    for (int i = 0; i < mod; ++i)
        if (dp[n][m][i])
            ++ans;
    printf("%d\n", ans);
}