「BZOJ 5010」「FJOI 2017」矩阵填数「状压DP」

客官°小女子只卖身不卖艺 2023-06-05 12:51 48阅读 0赞

**题意**

你有一个\\(h\\times w\\)的棋盘，你需要在每个格子里填\\(\[1, m\]\\)中的某个整数，且满足\\(n\\)个矩形限制：矩形的最大值为某定值。求方案数\\(\\bmod 10^9+7\\)

\\(h, w, m\\leq 10^4,n\\leq 10\\)

**题解**

首先来考虑单独的一个矩形限制怎么做。假设矩形面积为\\(s\\)，最大值为\\(v\\)

易得答案是\\(v^\{s\}-(v-1)^\{s\}\\)，意思就是每个数随便选，然后减去所有数\\(<v\\)的方案

现在考虑\\(n\\)个限制，实际上把棋盘分成了\\(O(2^n)\\)个部分。注意这里，包含两个格子的矩形集合相同，则两个格子算一个部分，并不是按四连通来定义的。

那我们对于每一部分，假设有若干的矩形包含它，那这个部分能放的最大值是所有包含它的矩形的限制的最小值。

这就是说一个矩形限制，被分成若干部分，这些部分必须有一个取到最大值，就考虑状压DP

\\(dp\[i\]\[S\]\\)表示前i个部分，\\(S\\)集合里的矩形已经被满足，方案数是多少。

设当前部分\\(i\\)的大小为\\(sz\[i\]\\)，包含这个部分的矩形中限制恰好为当前部分限制\\(v\\)的矩形集合为\\(cov\[i\]\\)，当前部分的限制为\\(v\\)

要取到最大值：

\\(dp\[i + 1\]\[j\] += dp\[i\]\[j\]\\times (v-1)^\{sz\[i\]\}\\)

不取最大值：

\\(dp\[i + 1\]\[j | cov\[i\]\] += dp\[i\]\[j\](v^\{sz\[i\]\} - (v-1)^\{sz\[i\]\})\\)

然后就很暴力地做完了。

比较新奇的是每个部分实际面积的求法（我没见过），对于每个交集，原大小减去子集的实际面积大小

代码更加直观地展现我在说什么。

#include <algorithm>
    #include <cstdio>
    using namespace std;
    
    const int mo = 1e9 + 7;
    const int N = 10;
    
    struct matrix {
        int x1, y1, x2, y2, d;
        void operator &= (const matrix &b) {
            d = min(d, b.d);
            x1 = max(x1, b.x1);
            y1 = max(y1, b.y1);
            x2 = min(x2, b.x2);
            y2 = min(y2, b.y2);
            if(x1 > x2 || y1 > y2) d = -1;
        }
    } a[N], b[1 << N];
    int h, w, m, n, t, dp[1100][1 << N], cov[1 << N], sz[1 << N], st[1 << N], sum;
    
    void dfs(int u, matrix mat, int s) {
        if(u == n) { b[s] = mat; return ; }
        dfs(u + 1, mat, s); mat &= a[u];
        dfs(u + 1, mat, s | (1 << u));
    }
    
    int qpow(int a, int b) {
        int ans = 1;
        for(; b >= 1; b >>= 1, a = 1ll * a * a % mo)
            if(b & 1) ans = 1ll * ans * a % mo;
        return ans;
    }
    void chk(int &u) { u >= mo ? u -= mo : 0; }
    
    int main() {
        int te; scanf("%d", &te);
        while(te --) {
            scanf("%d%d%d%d", &h, &w, &m, &n);
            for(int i = 0; i < n; i ++)
                scanf("%d%d%d%d%d", &a[i].x1, &a[i].y1, &a[i].x2, &a[i].y2, &a[i].d);
            dfs(0, (matrix) {1, 1, h, w, m}, 0);
            for(int i = 0; i < (1 << n); i ++) sz[i] = b[i].d == -1 ? 0 : (b[i].x2 - b[i].x1 + 1) * (b[i].y2 - b[i].y1 + 1);
            for(int i = (1 << n) - 1; i >= 1; i --) {
                sz[0] -= sz[i];
                for(int j = (i - 1) & i; j; j = (j - 1) & i) sz[j] -= sz[i];
            }
            t = 0;
            for(int i = 1; i < (1 << n); i ++) if(sz[i] >= 1) {
                cov[i] = 0;
                for(int j = 0; j < n; j ++) if((i >> j & 1) && a[j].d == b[i].d) cov[i] |= 1 << j;
            }
            for(int i = 1; i < (1 << n); i ++) if(sz[i] >= 1) st[++ t] = i;
            for(int i = 0; i <= t; i ++) fill(dp[i], dp[i] + (1 << n), 0);
            dp[0][0] = 1;
            for(int i = 0; i < t; i ++) {
                int nd = sz[st[i + 1]], up = b[st[i + 1]].d;
                int t1 = qpow(up, nd), t2 = qpow(up - 1, nd);
                for(int s = 0; s < (1 << n); s ++) if(dp[i][s]) {
                    chk(dp[i + 1][s] += 1ll * dp[i][s] * t2 % mo);
                    chk(dp[i + 1][s | cov[st[i + 1]]] += 1ll * dp[i][s] * (t1 - t2 + mo) % mo);
                }
            }
            printf("%d\n", 1ll * qpow(m, sz[0]) * dp[t][(1 << n) - 1] % mo);
        }
        return 0;
    }

转载于:https://www.cnblogs.com/hongzy/p/11339854.html