C++14(g++5.4) 解法, 执行用时: 20ms, 内存消耗: 13176K, 提交时间: 2020-09-21 23:24:01

#include<bits/stdc++.h>
using namespace std;
bitset<10007>B[110][110],x,y,z;
int mo=1e4+7,A[110][110];
int main()
{
	int i,n,m,a,j;
	cin>>n>>m;
	for(i=1;i<=n;i++)
	for(j=1;j<=m;j++)
	cin>>A[i][j];
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		{
			a=A[i][j]%mo;
			z=B[i-1][j]|B[i][j-1];
			x=z<<a;
			y=z>>(mo-a);
			B[i][j]=x|y;
			if(i==1&&j==1)
			B[1][1][a]=1;
		}
	}
	cout<<B[n][m].count()<<endl;
}

C++(clang++11) 解法, 执行用时: 15ms, 内存消耗: 12792K, 提交时间: 2021-02-18 20:42:55

#include<cstdio>
#include<bitset>
#define mod 10007
using namespace std;
int n,m,a;
bitset<mod>bs[101][101],l;
int main() {
	scanf("%d %d",&n,&m);
	bs[0][1][0]=1;
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=m;j++) {
			scanf("%d",&a);
			a%=mod;
			l=(bs[i-1][j]|bs[i][j-1]);
			bs[i][j]=((l<<(mod-a))|(l>>a));
		}
	}
	printf("%d",bs[n][m].count());
	return 0;
}