题解 P3813 【[FJOI2017]矩阵填数】

· · 题解

敲代码的时候懒得切输入法所以注释全是英文emmm

作为本蒻的一个心结，这道题的细节还是蛮多的。

做法就是 离散化坐标 + 状压DP。

下面这段内容摘录自FJWC2017课件。

题意：一个矩阵中可以任意填 m 个数。给你 N 个小矩阵并且告诉你此矩阵中的最大值 v，求有多少种大矩阵满足所给条件。

分析：考虑到 n 很小，因此我们可以通过离散化将所有不同的矩阵重叠的情况(最多 2 ^ n种)的最大值和块数先处理出来。其中第 i 种的最大值为 v_i，块数为 c_i。 然后对于每一种重叠情况，我们有两种选择，其一是不取最大值，则方案数为(v_i - 1) ^{c_i}。第二种是取最大值，则方案数为 v_i ^ {c_i} - (v_i - 1) ^ {c_i}。

则可以设 dp[i][j]为前 i 种重叠块其中有 j 这些状态的矩阵的最大值被满足了的方案数，则我们现在考虑第 i+1 块的取的情况。不妨设当第 i+1 块取最大值时能使得 s[i + 1]的矩阵被满足。

则当取最大值时，把对应方案数转移到 dp[i + 1][j | s[i + 1]]，否则转移到 dp[i + 1][j]。

故 dp[(1 << n)][(1 << n) - 1]为最终的方案。

具体实现细节请参考本蒻的代码。

#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 10010
#define maxm 30
#define mod 1000000007
#define Lovelive long long

// Records the matrices' information.
int x1[maxm], y1[maxm], x2[maxm], y2[maxm], v[maxm];

// Represents x-bounds && y-bounds.  
// e.g. xb[i] = 1 means that there is a gap between row 1 and row 2. 
int xb[maxm], yb[maxm], xbs, ybs;

// Record the information for each block.
int block[maxm * maxm], bs, blimit[maxm * maxm], fulfill[maxm * maxm];

// DP array.
Lovelive f[maxm * maxm][1100];

// Tell whether the grid (x,y) is in rectangle i.
inline int in(int x, int y, int i) {
    return x >= x1[i] && x <= x2[i] && y >= y1[i] && y <= y2[i];
}

// Returns the minimum value between x and y.
inline int min(int x, int y) {
    return x < y ? x : y;
}

// Calculate power of an integer in O(log p) time
Lovelive pow(Lovelive n, Lovelive p) {
    Lovelive ret = 1;
    for(; p; p >>= 1, n = n * n % mod) {
        if(p&1) ret = ret * n % mod;
    }
    return ret;
}

int main() {
    int T;
    scanf("%d", &T);
    while(T--) {
        //initialization 
        xbs = ybs = bs = 0;
        xb[xbs++] = 0;
        yb[ybs++] = 0;
        memset(f, 0, sizeof f);
        memset(fulfill, 0, sizeof fulfill);

        int h, w, m, n;
        scanf("%d%d%d%d", &h, &w, &m, &n);
        for(int i = 0; i < n; i++) {
            scanf("%d%d%d%d%d", x1 + i, y1 + i, x2 + i, y2 + i, v + i);
            xb[xbs++] = x1[i] - 1;
            yb[ybs++] = y1[i] - 1;
            xb[xbs++] = x2[i];
            yb[ybs++] = y2[i];
        }
        xb[xbs++] = h;
        yb[ybs++] = w;
        // Discretize indices.
        std::sort(xb, xb + xbs);
        std::sort(yb, yb + ybs);
        xbs = std::unique(xb, xb + xbs) - xb;
        ybs = std::unique(yb, yb + ybs) - yb;

        // Preprocess the information of each block.
        for(int i = 1; i < xbs; ++i) {
            for(int j = 1; j < ybs; ++j) {
                ++bs;
                block[bs] = (xb[i] - xb[i-1]) * (yb[j] - yb[j-1]);
                blimit[bs] = m;
                for(int k = 0; k < n; ++k)
                    if(in(xb[i], yb[j], k))
                        blimit[bs] = min(blimit[bs], v[k]);                
                for(int k = 0; k < n; ++k)
                    if(in(xb[i], yb[j], k) && blimit[bs] == v[k])
                        fulfill[bs] ^= 1 << k;
            }
        }

        int li = 1 << n;
        f[0][0] = 1;
        for(int i = 1; i <= bs; ++i) {
            int ful = fulfill[i];
            Lovelive fail = pow(blimit[i] - 1, block[i]);
            Lovelive success = pow(blimit[i], block[i]) - fail + mod;
            for(int j = 0; j - li; ++j) {
                f[i][j] = (f[i][j] + f[i-1][j] * fail) % mod;
                f[i][j|ful] = (f[i][j|ful] + f[i-1][j] * success) % mod;
            }
        }

        printf("%d\n", (int)f[bs][li-1]);
    }
}