LibreOJ 3136 「COCI 2019.03」Mobitel

首先有一个很显然的状态：fi,j,k 表示走到 (i,j)，乘积为 k 的方案数。
特别地，当 k=n 时表示乘积不小于 k 的方案数。

但是这样子是 O(rsn) 的。

如果我们把状态换一下，变成 fi,j,k 表示走到 (i,j)，乘积至少乘 k 后不小于 n 的方案数。
看起来并没有什么变化……

但是，这样子的话，有用的 k 都形如 ⌈nd⌉。
类似数论分块，可以证明最多只有 O(√n) 种。

于是我们把有用的 k 重新标号（即离散化），然后跑 DP，同时滚动第一维（你要把第二维一起滚了也行 QwQ）。
这样子就得到了一个 O(rs√n) 的算法。

代码：

#include <cstdio>
#include <cmath>
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);
}