分析

因为一个节点 只有可能从 转移过来。考虑枚举余数，那么令 表示在节点 数字 是否可以表达。那么答案为 。

代码

#include<bits/stdc++.h>
using namespace std;
int read() {
    int x = 0,f = 0;char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-') f = 1;ch = getchar();}
    while(isdigit(ch)) {x = x*10 + ch - '0';ch = getchar();}
    return f?-x:x;
}
const int N = 110,mod = 1e4 + 7;
int n,m,val[N][N];
bool f[N][N][11000];
signed main() {
    n = read();m = read();
    for(int i = 1;i <= n;i++) {
        for(int j = 1;j <= m;j++) {
            val[i][j] = read()%mod;
        }
    }
    f[1][1][val[1][1]] = 1;
    for(int i = 1;i <= n;i++) {
        for(int j = 1;j <= m;j++) {
            if(i == 1 && j == 1) continue;
            for(int k = 0;k < mod;k++) {
                f[i][j][(val[i][j]+k)%mod] |= f[i-1][j][k];
                f[i][j][(val[i][j]+k)%mod] |= f[i][j-1][k];
            }
        }
    }
    int ans = 0;
    for(int k = 0;k < mod;k++) {
        if(f[n][m][k]) ans = ans + 1;
    }
    cout << ans << endl;
    return 0;
}