「Codeforces 295D」Greg and Caves

给定\(n,m\)，你需要对一个\(n\times m\)的矩阵黑白染色，满足：

1. 存在一个区间\([l,r]\)，满足\(l\sim r\)这些行有且仅有两个黑色格子，其他行不存在黑色格子。
2. 存在一个\(t\ (l\le t\le r)\)，使得对于所有的\(i,j\ (l\le i\le j\le t)\)，满足第\(i\)行以两个黑色格子为端点的区间（以下简称“区间”）被\(j\)行的区间包含；同样地，对于所有的\(i,j\ (t\le i\le j\le r)\)，第\(j\)行的区间被第\(i\)行的区间包含。

求染色方案数\(\bmod (10^9+7)\)的值。

比较简单的\(\mathrm{DP}\)，设\(dp_{i,j}\)表示上半部分（即\(l\)到\(t\)部分）的高度至多为\(i\)，底边宽度（包含两个黑色格子）为\(j\)且底边位置固定时的方案数。

转移方程

\[dp_{i,j}=dp_{i,j-1}+\sum\limits_{k=2}^j dp_{i-1,k}\]

应该还是比较好理解的。初始值\(dp_{1,i}=dp_{i,1}=1\)。

直接转移是\(O(n^3)\)的，但是\(\sum\limits_{k=2}^j dp_{i-1,k}\)可以在枚举\(j\)的同时计算（即前缀和优化），时间复杂度可以做到\(O(n^2)\)。

答案

下半部分的方案与上半部分同理。

注意如果下半部分的底边长度和上半部分的底边长度相等，会有重复，所以应该减去。

\[ans=\sum\limits_{i=1}^n \sum\limits_{j=2}^m (dp_{i,j}-dp_{i-1,j})\times dp_{n-i+1,j}\times (m-j+1)\bmod 1000000007\]

\(i\)枚举的是下半部分的起始位置，\(j\)枚举的是下半部分的底边宽度，第一项是上半部分减去长度相等的方案，第二项是下半部分的方案，第三项是计算底边在矩阵中的位移。

注意需要随时取模。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

#include <cstdio>
#define P 1000000007
int n, m, dp[2005][2005], ans;
int main(){
    scanf("%d%d", &n, &m);
    for (register int i = 1; i <= m; ++i) dp[1][i] = 1;
    for (register int i = 2; i <= n; ++i){
        int s = 0;
        dp[i][1] = 1;
        for (register int j = 2; j <= m; ++j)
            (s += dp[i - 1][j]) %= P, dp[i][j] = (dp[i][j - 1] + s) % P; // 前缀和优化
    }
    for (register int i = 1; i <= n; ++i)
        for (register int j = 2; j <= m; ++j)
            (ans += 1ll * (dp[i][j] - dp[i - 1][j] + P) * dp[n - i + 1][j] % P * (m - j + 1) % P) %= P; // 计算答案，随时取模
    printf("%d", ans);
}