题解：CF273D Dima and Figure

· · 题解

跟出题人对上脑电波了。

题目大意：一个 n \times m 的矩阵，你可以将部分格子涂黑，一个涂黑方案合法当且仅当黑部分联通且任意两黑点都存在一条最短路上全是黑点。

dp。

我们考虑构造方案的双射，我们发现原方案合法当且仅当每一行的涂黑部分都是连续的且左右边界都不超过单峰。

根据这个双射，我们可以分别对于左右边界的升、降部分进行 dp。

具体的，记 f_{i, l, r, 0/1, 0/1} 为仅填入连续 i 行的情况下，被填入的第 i 行的涂黑部分是 [l, r]、左右分别还是否可以向外的方案（即是否已经存在一个峰）的情况下的方案数。

转移比较简单吧，考虑一下左右是否能扩展就行。然后把 i 滚掉。然而复杂度是 \mathcal{O}(n^5)，过不了。

考虑前缀和思想转移（完全背包），对于每一轮 i，每次只转移相邻的两种状态，这样也能转移成功。复杂度很优秀，\mathcal{O}(n^3)。

:::info[code]

#include <bits/stdc++.h>
//#define fastio
#define int long long
#define bw(x) (1 << x)
#define eb emplace_back
#define pii pair<int, int>
#define inf (0x3f3f3f3f3f3f3f3f)
#define F(x, v) for (auto x : (v))
#define ALL(x) (x).begin(), (x).end()
#define L(i, a, b) for (register int i = (a); i <= (b); ++i)
#define R(i, a, b) for (register int i = (a); i >= (b); --i)
#define FRE(i, o) freopen(i, "r", stdin), freopen(o, "w", stdout)
using namespace std; bool bgmem;
#ifdef fastio
struct IO {
    #define ion bw(20)
    char i[ion], o[ion], *icl = i, *icr = i, *oc = o;
    char gc() { return (icl == icr && (icr = (icl = i) + fread(i, 1, ion, stdin), icl == icr)) ? EOF : *icl++; }
    void pc(char c) { if (oc - o == ion) fwrite(o, 1, ion, stdout), oc = o; *oc++ = c; }
    void rd(auto &x) { char c; int f = 1; x = 0; while (c = gc(), c < '0' || c > '9') if (c == '-') f = -1; while ('0' <= c && c <= '9') x = (x << 1) + (x << 3) + (c ^ 48), c = gc(); x *= f; } 
    void pr(auto x) { int a[64], p = 0; if (x < 0) x = -x, pc('-'); do a[p++] = x % 10; while (x /= 10); while (p--) pc(a[p] + '0'); } 
    IO& operator>>(char &c) { return c = gc(), *this; }
    IO& operator<<(char c) { return pc(c), *this; }
    IO& operator<<(const char *c) { while (*c) pc(*c++); return *this; }
    IO& operator>>(auto &x) { return rd(x), *this; }
    IO& operator<<(auto x) { return pr(x), *this; }
} io;
#define cin io
#define cout io
#endif
const int N = 155, P = 1e9 + 7;
inline int cmax(int& x, int c) { return x = max(x, c); }
inline int cmin(int& x, int c) { return x = min(x, c); }
int tes = 1, cas;
namespace zrh {
    int n, m, dp[N][N][2][2], ret, ans; 
    void init() {}
    void clear() {}
    void solve() {  
        cin >> n >> m;
        L(l, 1, m) L(r, l, m) ret = (ret + (dp[l][r][1][1] = 1)) % P; ans = (ans + ret * n % P) % P;
        L(i, 2, n) {
            L(r, 1, m) L(l, 1, r - 1) L(c, 0, 1) dp[l + 1][r][0][c] = (dp[l + 1][r][0][c] + dp[l][r][0][c] + dp[l][r][1][c]) % P;
            L(l, 1, m) R(r, m, l + 1) L(c, 0, 1) dp[l][r - 1][c][0] = (dp[l][r - 1][c][0] + dp[l][r][c][0] + dp[l][r][c][1]) % P;
            L(r, 1, m) R(l, r, 1 + 1) L(c, 0, 1) dp[l - 1][r][1][c] = (dp[l - 1][r][1][c] + dp[l][r][1][c]) % P;
            L(l, 1, m) L(r, l, m - 1) L(c, 0, 1) dp[l][r + 1][c][1] = (dp[l][r + 1][c][1] + dp[l][r][c][1]) % P;
            ret = 0; L(l, 1, m) L(r, l, m) L(cl, 0, 1) L(cr, 0, 1) ret = (ret + dp[l][r][cl][cr]) % P; 
            ans = (ans + ret * (n - i + 1) % P) % P;
        }
        cout << ans << "\n";
    }
} bool edmem; signed main() {
    // FRE("", "");
#ifndef fastio
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#endif
    // cin >> tes;
    zrh::init(); while (++cas <= tes) zrh::clear(), zrh::solve();
#ifdef fastio
    fwrite(io.o, 1, io.oc - io.o, stdout);
#endif
    cerr << "time  : " << (double)clock() / CLOCKS_PER_SEC * 1000 << "ms\n";
    cerr << "memory: " << fabs(&edmem - &bgmem) / 1024 / 1024 << "mb\n";
    return 0;
}
// I will never love zrh again. =(

:::