LibreOJ 3136 「COCI 2019.03」Mobitel

首先有一个很显然的状态：\(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)\) 的算法。

代码：

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