首先有一个很显然的状态：\(f_{i,j,k}\) 表示走到 \((i,j)\)，乘积为 \(k\) 的方案数。
特别地，当 \(k = n\) 时表示乘积不小于 \(k\) 的方案数。
但是这样子是 \(O(rsn)\) 的。
如果我们把状态换一下，变成 \(f_{i,j,k}\) 表示走到 \((i,j)\)，乘积至少乘 \(k\) 后不小于 \(n\) 的方案数。
看起来并没有什么变化……
但是，这样子的话，有用的 \(k\) 都形如 \(\lceil \dfrac n d \rceil\)。
类似数论分块，可以证明最多只有 \(O(\sqrt n)\) 种。
于是我们把有用的 \(k\) 重新标号（即离散化），然后跑 DP，同时滚动第一维（你要把第二维一起滚了也行 QwQ）。
这样子就得到了一个 \(O(rs \sqrt n)\) 的算法。
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
using namespace std;
const int R = 300;
const int S = 300;
const int N = 1e6;
const int CNT = 2e3;
const int mod = 1e9 + 7;
int r,s,n;
int a[R + 5][S + 5];
int val[N + 5],id[N + 5],cnt;
int f[2][S + 5][CNT + 5];
int ans;
int main()
{
scanf("%d%d%d",&r,&s,&n);
val[++cnt] = n,id[n] = cnt;
for(register int i = 2;i <= n;++i)
if((int)ceil((double)n / i) ^ (int)ceil((double)n / (i - 1)))
val[++cnt] = ceil((double)n / i),id[(int)ceil((double)n / i)] = cnt;
for(register int i = 1;i <= r;++i)
for(register int j = 1;j <= s;++j)
scanf("%d",a[i] + j);
f[0][1][id[(int)ceil((double)n / a[1][1])]] = 1;
for(register int i = 1,cur = 0;i <= r;++i,cur ^= 1)
for(register int j = 1;j <= s;++j)
for(register int k = 1;k <= cnt;++k)
{
if(i < r)
f[cur ^ 1][j][id[(int)ceil((double)val[k] / a[i + 1][j])]] = (f[cur ^ 1][j][id[(int)ceil((double)val[k] / a[i + 1][j])]] + f[cur][j][k]) % mod;
if(j < s)
f[cur][j + 1][id[(int)ceil((double)val[k] / a[i][j + 1])]] = (f[cur][j + 1][id[(int)ceil((double)val[k] / a[i][j + 1])]] + f[cur][j][k]) % mod;
if(i == r && j == s && k == cnt)
ans = f[cur][j][k];
f[cur][j][k] = 0;
}
printf("%d\n",ans);
}