Codeforces 295D Greg and Caves

首先可以只考虑有效的行（有黑格的），设有 \(h\) 行，那么就有 \(n - h + 1\) 种分配方式，最后 \(\times (n - h + 1)\) 即可。

对于有效的行，发现如果要考虑中间的部分 \([l, r]\) 其实可以只用 \(len = r - l + 1\) 来表示。
当然肯定会漏掉一些方案的，但考虑知道了 \(\max\{len\}\) 之后，再在列中选，即 \(\times (m - \max\{len\} + 1)\) 就可以了。

因为题目要求了 \(len\ge 2\)，不妨令 \(len\leftarrow len - 2, m\leftarrow m - 2\)，就变成了 \(len\ge 0\)。

于是可以考虑 \(\text{DP}\)，令 \(f_{i, j}\) 为第 \(i\) 行 \(len = j\) 的方案数。
但是发现即可以增大又可以减小，且 \(\max\) 也不好处理，再令 \(f\) 要满足 \(len\) 不减。
转移式即为 \(f_{i, j} = \sum\limits_{k = 0}^j (j - k + 1)f_{i - 1, k}\)，考虑做差分有 \(f_{i, j} - f_{i, j - 1} = \sum\limits_{k = 0}^j f_{i - 1, k}\)，便可以 \(\mathcal{O}(nm)\) 求出来了。

此时就可以知道 \(\max\{len\}\) 的值了，相当于就是最后的 \(j\)，于是有 \(f_{i, j}\leftarrow f_{i, j}\times (m - j + 1)\)。

接下来就考虑把递减的那部分同样 \(\text{DP}\) 求出来。
类似的，令 \(g_{i, j}\) 为不增，且包括前面不降的部分已经有 \(i\) 行了 \(len = j\) 的方案数。
转移时即为 \(g_{i, j} = \sum\limits_{k = j}^m (k - j + 1)g_{i - 1, k} + \sum\limits_{k = j + 1}^m (k - j + 1)f_{i - 1, k}\)，这里的 \(f\) 转移不一样是为了避免 \(\max\{len}\) 有多行导致记重的情况。
一样的可以用差分的方法，时间复杂度 \(\mathcal{O}(nm)\)。

同时还需注意，\(g\) 是保证了 \(\max\) 后肯定是有至少一行降的，这会导致算漏 \(\max\) 后面没有有效行的方案数，把 \(f\) 也记入答案即可。

时间复杂度 \(\mathcal{O}(nm)\)。

#include<bits/stdc++.h>
using ll = long long;
constexpr ll mod = 1e9 + 7;
const int maxn = 2e3 + 10;
ll f[maxn][maxn], s[maxn][maxn], g[maxn][maxn];
int main() {
   int n, m;
   scanf("%d%d", &n, &m);
   m -= 2;
   for (int i = 0; i <= m; i++)
      f[1][i] = 1;
   for (int i = 2; i <= n; i++) {
      ll sum = 0;
      for (int j = 0; j <= m; j++) {
         (sum += f[i - 1][j]) %= mod;
         f[i][j] = ((! j ? 0 : f[i][j - 1]) + sum) % mod;
      }
   }
   for (int i = 1; i <= n; i++)
      for (int j = 0; j <= m; j++)
         (f[i][j] *= m - j + 1) %= mod;
   ll ans = 0;
   for (int i = 1; i <= n; i++)
      for (int j = 0; j <= m; j++)
         (ans += f[i][j] * (n - i + 1)) %= mod;
   for (int i = 2; i <= n; i++) {
      ll sum = 0;
      for (int j = m; j >= 0; j--) {
         (sum += f[i - 1][j]) %= mod;
         s[i][j] = ((j == m ? 0 : s[i][j + 1]) + sum) % mod;
      }
      for (int j = 0; j <= m; j++)
         (s[i][j] += mod - f[i - 1][j]) %= mod;
   }
   for (int i = 2; i <= n; i++) {
      ll sum = 0;
      for (int j = m; j >= 0; j--) {
         (sum += g[i - 1][j]) %= mod;
         (g[i][j] += (j == m ? 0 : g[i][j + 1]) + sum) %= mod;
      }
      for (int j = 0; j <= m; j++)
         (g[i][j] += s[i][j]) %= mod;
   }
   for (int i = 1; i <= n; i++)
      for (int j = 0; j <= m; j++)
         (ans += g[i][j] * (n - i + 1)) %= mod;
   printf("%lld\n", ans);
   return 0;
}