题意

牛牛可以在n*m的图中向右走或者向下走，每个点有一个权值，经过某点获得该点权值并对1e4+7求模，问从(1,1)走到(n,m)，在(n,m)点存在多少种权值情况。

题解

设一个dp三维布尔数组，dp[i][j][k]表示从(1,1)走到(i,j)点是否在(i,j)点可以产生k的权值。
易知转移方程

即当前位置只能由上面一格或左面一格转移而来,且若想权值可以为k，则转移前的权值需要为

code

#include <bits/stdc++.h>
#define reg register
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define inf 0x3f3f3f3f
#define eps 1e-8
#define pi acos(-1.0)
#define e exp(1.0)
#define ios ios::sync_with_stdio(false)
#define rep(i,l,r) for(int i=(l);i<(r);i++)
using namespace std;

const int maxn = 100 + 10;
const int mod = 1e4 + 7;

int n,m;
int v[maxn][maxn];
bool dp[105][105][10010];

int main()
{
   cin>>n>>m;
   for(int i = 1;i <= n;++i){
      for(int j = 1;j <=m;++j){
         cin>>v[i][j];
         v[i][j] %= mod;
      }
   }
   dp[1][1][v[1][1]] = 1;
   for(int i = 1;i <= n;++i){
      for(int j = 1;j <= m;++j){
         for(int k = 0;k < mod;++k){
            dp[i][j][k] |= dp[i-1][j][(k-v[i][j]+mod) % mod];
            dp[i][j][k] |= dp[i][j-1][(k-v[i][j]+mod) % mod];
         }
      }
   }
   int res = 0;
   for(int i = 0;i < mod;++i) res += dp[n][m][i];
   printf("%d\n",res);

   return 0;
}