题解 CF295D 【Greg and Caves】
xtx1092515503
2020-10-12 18:50:44
# [Portal](https://www.luogu.com.cn/problem/CF295D)
首先一眼就能看出一个DP状态：
我们设 $f_{i,j,k}$ 表示填了 $i$ 行（即这个洞占了 $i$ 行），且第 $i$ 行的洞是在区间 $[j,k]$，且这 $i$ 行中都有 $S_{i-1}\subseteq S_i$ 的方案数。
则我们有显然的转移方程：
$$f_{i,j,k}=\sum\limits_{[l,r]\subseteq[j,k]}f_{i-1,l,r}$$
显然这个可以被一个二维前缀和优化到 $O(m^2)$ 地从 $f_{i-1}$ 推到 $f_i$。
然后我们发现我们并不关心这个区间 $[j,k]$ 到底在哪——我们只关心它的长度。
于是我们可以轻松消减掉一维。我们设 $f_{i,j}$ 表示填了 $i$ 行，且当前行上洞的长度是 $j$ 的方案数。
则有
$$f_{i,j}=f_{i-1,j}+2\times f_{i,j-1}-f_{i,j-2}$$
使用的是二维前缀和的递推方式。
则我们最终要求出答案。显然它是由两半拼在一起（前一半的区间是递增的，后一半的区间是递减）得到的。
故我们可以得出答案为
$$\sum\limits_{i+j\leq n+1}\sum\limits_{k=2}^mf_{i,k}\times f_{j,k}\times(m-k+1)$$
其中 $(m-k+1)$ 是因为整个 $m$ 的大区间一共可以挖出这么多长度为 $k$ 的小区间。
明显我们在 $j$ 这一维上做一个前缀和即可做到总复杂度为 $O(nm)$。
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int n,m,f[2010][2010],res,g[2010][2010];
int main(){
scanf("%d%d",&n,&m);
for(int i=2;i<=m;i++)f[1][i]=1;
for(int i=2;i<=n;i++)for(int j=2;j<=m;j++)(f[i][j]=(0ll+f[i-1][j]+f[i][j-1]*2-f[i][j-2]+mod)%mod);
for(int i=1;i<=n;i++)for(int j=2;j<=m;j++)g[i][j]=(g[i-1][j]+f[i][j])%mod;
for(int i=1;i<=n;i++)for(int j=2;j<=m;j++)(res+=1ll*f[i][j]*g[n+1-i][j]%mod*(m-j+1)%mod)%=mod;
printf("%d\n",res);
return 0;
}
```