1 条题解
-
1
题意
问满足下列条件的 的 01 矩阵 的数量：
- ，满足 且 。
- 设 中的每一行的第一个值为 的位置的下标为 ，第二个值为 的位置的下标为 ，则：，满足 $\forall i \in [l,~t-1],~x_i \ge x_{i+1},~y_i \le y_{i+1}$ 且 $\forall i \in [t,~r-1],~x_i \le x_{i+1},~y_i \ge y_{i+1}$。
分析
考虑使用 DP 解决本题。
令 表示考虑洞的前 行（该 行都在洞的中间位置 的上方）且第 行的 时该洞的构造方案（不考虑洞在矩阵中的摆放位置）。
考虑枚举第 行的长度以及与第 行的相对位置，得出转移方程：
尝试使用该数据描述最终答案 ，考虑枚举中间位置 的行编号以及该行 的大小。同时由于可能存在构造洞的方案满足第 行与相邻的几行的形态完全相同，为了防止算重，考虑令 为洞的最大的满足 最大的行数，同时枚举 行的长度（小于 行长度），算出最终答案：
$$\begin{aligned} Ans&=\sum_{i=1}^{n} \sum_{a=0}^{m-2} (m-a-1) \times \big( \sum_{l=1}^{i} f[i-l+1][a] \big) \times (1 + \sum_{b=0}^{a-1} \big( \sum_{r=i+1}^{n} f[r-i][b] \big) \times (a - b + 1))\\\\ &=\sum_{i=1}^{n} \sum_{a=0}^{m-2} (m-a-1) \times \big( \sum_{t=1}^{i} f[t][a] \big) \times (1 + \sum_{b=0}^{a-1} \big( \sum_{t=1}^{n-i} f[t][b] \big) \times (a - b + 1)) \end{aligned} $$令 。
$$Ans=\sum_{i=1}^{n} \sum_{a=0}^{m-2} (m-a-1) \times g[i][a] \times (1 + \sum_{b=0}^{a-1} g[n-i][b] \times (a-b+1)) $$令 。
$$Ans=\sum_{i=1}^{n} \sum_{a=0}^{m-2} (m-a-1) \times g[i][a] \times (1 + h[n-i][a]) $$处理 前缀和优化到 ，处理 ，处理 前缀和优化到 ，计算答案 。
总时间复杂度 。
代码
Code
/** * @author Macesuted (macesuted@outlook.com) * @copyright Copyright (c) 2021 * @brief * My solution: https://macesuted.moe/article/cf295d */ #include <bits/stdc++.h> using namespace std; namespace io { #define SIZE (1 << 20) char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55]; int f, qr; inline void flush(void) { return fwrite(obuf, 1, oS - obuf, stdout), oS = obuf, void(); } inline char getch(void) { return (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS++)) : *iS++); } inline void putch(char x) { *oS++ = x; if (oS == oT) flush(); return; } string getstr(void) { string s = ""; char c = getch(); while (c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == EOF) c = getch(); while (!(c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == EOF)) s.push_back(c), c = getch(); return s; } void putstr(string str, int begin = 0, int end = -1) { if (end == -1) end = str.size(); for (register int i = begin; i < end; i++) putch(str[i]); return; } template <typename T> inline T read() { register T x = 0; for (f = 1, c = getch(); c < '0' || c > '9'; c = getch()) if (c == '-') f = -1; for (x = 0; c <= '9' && c >= '0'; c = getch()) x = x * 10 + (c & 15); return x * f; } template <typename T> inline void write(const T& t) { register T x = t; if (!x) putch('0'); if (x < 0) putch('-'), x = -x; while (x) qu[++qr] = x % 10 + '0', x /= 10; while (qr) putch(qu[qr--]); return; } struct Flusher_ { ~Flusher_() { flush(); } } io_flusher_; } // namespace io using io::getch; using io::getstr; using io::putch; using io::putstr; using io::read; using io::write; #define maxn 2005 #define mod 1000000007 long long f[maxn][maxn], g[maxn][maxn], h[maxn][maxn], cac[maxn][maxn]; int main() { int n = read<int>(), m = read<int>(); for (register int i = 0; i <= m - 2; i++) f[1][i] = 1; for (register int i = 2; i <= n; i++) { f[i][0] = cac[i][0] = f[i - 1][0]; for (register int j = 1; j <= m - 2; j++) cac[i][j] = (cac[i][j - 1] + f[i - 1][j]) % mod, f[i][j] = (f[i][j - 1] + cac[i][j]) % mod; } for (register int i = 1; i <= n; i++) for (register int j = 0; j <= m - 2; j++) g[i][j] = (g[i - 1][j] + f[i][j]) % mod; memset(cac, 0, sizeof(cac)); for (register int i = 1; i < n; i++) for (register int j = 1; j <= m - 2; j++) cac[i][j] = (cac[i][j - 1] + g[i][j - 1]) % mod, h[i][j] = (h[i][j - 1] + cac[i][j] + g[i][j - 1]) % mod; long long answer = 0; for (register int i = 1; i <= n; i++) for (register int j = 0; j <= m - 2; j++) answer = (answer + (m - j - 1) * g[i][j] % mod * (1 + h[n - i][j])) % mod; write(answer), putch('\n'); return 0; }
Macesuted
QWQ
LV 8
SU
@ 2022-2-22 19:12:18
- 1
