题解 CF295D 【Greg and Caves】

· · 题解

Portal

首先一眼就能看出一个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)。

代码：

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