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

**Update On 2020.3.6：修复了一些细节问题**

---

“子矩阵最大值等于 $v$ ”的方案数等于“子矩阵最大值小于等于$v$的方案数”减去“子矩阵最大值小于 $v$ 的方案数”，考虑容斥。$2^n$ 地枚举哪些子矩阵满足最大值小于 $v$，那么我们可以得到矩阵中每一个位置能够取到的最大值，设 $x_{i,j}$ 表示 $(i,j)$ 的最大取值，那么方案数就是 $\prod\limits_{i=1}^H \prod\limits_{j=1}^W x_{i,j}$。

复杂度 $O(2^nHW)$ 不能接受。发现矩形个数很少，所以有大量的位置取到的最大值相等。可以对横纵坐标离散化，处理出一些子矩形满足无论如何这个子矩形内部的最大值均相等。因为横纵坐标都只有 $O(n)$ 种，所以一共有 $O(n^2)$ 个这样的矩形，对于同一个矩形的贡献可以同时计算。再按照上面的方法做复杂度就是 $O(2^nn^3)$ 了，精细实现还可以做到 $O(n^3+2^nn^2)$。

```
#include<bits/stdc++.h>
//this code is written by Itst
using namespace std;

const int MOD = 1e9 + 7;
int arr[25][25] , X[25] , Y[25] , cntx , cnty , W , H , N , M , T , pos[11][5];

int poww(long long a , int b){
    int times = 1;
    while(b){
        if(b & 1) times = times * a % MOD;
        a = a * a % MOD; b >>= 1;
    }
    return times;
}

int main(){
#ifdef ONLINE_JUDGE
    freopen("in","r",stdin);
    freopen("out","w",stdout);
#endif
    ios::sync_with_stdio(0);
    for(cin >> T ; T ; --T){
        cin >> W >> H >> M >> N; cntx = cnty = 0;
        for(int i = 1 ; i <= N ; ++i){
            for(int j = 0 ; j < 5 ; ++j)
                cin >> pos[i][j];
            X[++cntx] = pos[i][0]; Y[++cnty] = pos[i][1];
            X[++cntx] = ++pos[i][2]; Y[++cnty] = ++pos[i][3];
        }
        X[++cntx] = 1; X[++cntx] = W + 1;
        Y[++cnty] = 1; Y[++cnty] = H + 1;
        sort(X + 1 , X + cntx + 1); cntx = unique(X + 1 , X + cntx + 1) - X - 1;
        sort(Y + 1 , Y + cnty + 1); cnty = unique(Y + 1 , Y + cnty + 1) - Y - 1;
        int ans = 0;
        for(int i = 0 ; i < 1 << N ; ++i){
            for(int j = 1 ; j < cntx ; ++j)
                for(int k = 1 ; k < cnty ; ++k)
                    arr[j][k] = M;
            for(int j = 1 ; j <= N ; ++j)
                for(int k = lower_bound(X + 1 , X + cntx + 1 , pos[j][0]) - X ; X[k] != pos[j][2] ; ++k)
                    for(int l = lower_bound(Y + 1 , Y + cnty + 1 , pos[j][1]) - Y ; Y[l] != pos[j][3] ; ++l)
                        arr[k][l] = min(arr[k][l] , pos[j][4] - (i >> (j - 1) & 1));
            int tmp = 1;
            for(int j = 1 ; j < cntx ; ++j)
                for(int k = 1 ; k < cnty ; ++k)
                    tmp = 1ll * tmp * poww(arr[j][k] , (X[j + 1] - X[j]) * (Y[k + 1] - Y[k])) % MOD;
            ans = (ans + MOD + (__builtin_popcount(i) & 1 ? -1ll : 1ll) * tmp) % MOD;
        }
        cout << ans << endl;
    }
    return 0;
}
```

正在渲染内容...