题目：输入 $n,m,k$，再输入一个 $n$ 行 $m$ 列矩阵，求有多少条线路从矩阵左上角到右下角的线路经过的所有数乘积超过 $k$，线路只能向下/右走。

就是一个根号分治优化 dp 做法，然后就 T 了。

#include <cstdio>
#include <cmath>
#include <cstring>
#define int long long

inline int min(const int x, const int y) {return x < y ? x : y;}
const int mod = 1e9 + 7;
int mp[1000005], mp2[1000005], cnt;
int a[305][305], f[2][305][2005];

signed main() {
	int n, m, k;
	scanf("%lld%lld%lld", &n, &m, &k);
	for (int i = 1; i <= n; ++ i)
	for (int j = 1; j <= m; ++ j) scanf("%lld", &a[i][j]);
	for (int i = 1; i <= k; ++ i)
		if (i == 1 || ceil(1.0 * k / i) != ceil(1.0 * k / (i - 1)))
			mp[i] = ++ cnt, mp2[cnt] = i;
	f[1][1][mp[(int)ceil(1.0 * k / a[1][1])]] = 1;
	for (register int i = 1, cur = 1; i <= n; ++ i, cur ^= 1) {
		memset(f[cur ^ 1], 0, sizeof f[0]);
		for (register int j = 1; j <= m; ++ j)
		for (register int K = 1; K <= cnt; ++ K) {
			if (i < n) {
				register int x = min(k, (k + mp2[K] - 1) / mp2[K] * a[i + 1][j]);
				x = mp[(k + x - 1) / x];
				f[cur ^ 1][j][x] = (f[cur ^ 1][j][x] + f[cur][j][K]) % mod;
			}
			if (j < m) {
				register int x = min(k, (k + mp2[K] - 1) / mp2[K] * a[i][j + 1]);
				x = mp[(k + x - 1) / x];
				f[cur][j + 1][x] = (f[cur][j + 1][x] + f[cur][j][K]) % mod;
			}
		}
	}
	printf("%lld\n", f[n & 1][m][1]);
}
···