洛谷 5307.「COCI 2019.03.09」Mobitel

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

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

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

但是,这样子的话,有用的 kk 都形如 nd\lceil \dfrac n d \rceil
类似数论分块,可以证明最多只有 O(n)O(\sqrt n) 种。

于是我们把有用的 kk 重新标号(即离散化),然后跑 DP,同时滚动第一维(你要把第二维一起滚了也行 QwQ)。
这样子就得到了一个 O(rsn)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
#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);
}