CTime_Pup_314

不能再颓废了

0%

[FJOI2017]矩阵填数

发表于 更新于 分类于 阅读次数： Valine：

题面描述

给定矩阵和多个子矩形权值，对矩阵填数满足给定子矩阵的最大值为权值，求方案数

题解

很容易想到容斥，但是我太菜了不知道怎么算，一直认为补集转换时由等于必须变为不等于，但是却没想到全集是可以自己定义的，这样就可以由等于变为小于了，剩下就比较好办了，离散化后分割矩阵即可 具体来说我们定义问题的全集 \(S\) 每个元素的值域为 \([1,\ min(m,v_k)]\) 我们现在对限制进行补集转化，变为性质 \(p_k=w_{i,j}<v_k\)，具有该性质的集合为 \(A_k\) ，我们现在要求求出不满足任意一条性质的方案数 \(T\)，根据组合容斥公式 \[ T\ =\ |S|-\sum_{k=1}^n(-1)^k\sum_{1\le i_1<i_2<...<i_k\le n}|A_{i_1}\cap A_{i_2}\cap ...\cap A_{i_k}| \]

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <cstdio>
#include <algorithm>
#include <cctype>
using namespace std;
inline int read(int f = 1, int x = 0, char ch = ' ')
{
    while(!isdigit(ch = getchar())) if(ch == '-') f = -1;
    while(isdigit(ch)) x = x*10+ch-'0', ch = getchar();
    return f*x;
}
const int P = 1e9+7, N = 1e3+5;
inline int qpow(int a, int b)
{
    int ret = 1;
    for( ; b; b >>= 1, a = 1ll*a*a%P) if(b&1) ret = 1ll*ret*a%P;
    return ret;
}
int n, a, b, m;
int t, tx, ty, tv;
int xs[N], ys[N], vs[N], w[N][N], fv[N][N], c[N];
int x1[N], y1[N], x2[N], y2[N], v[N];
int ans;
signed main()
{
    t = read();
    while(t--)
    {
        a = read(), b = read(), m = read(), n = read();
        tx = ty = tv = ans = 0; 
        xs[++tx] = 1; xs[++tx] = a+1; 
        ys[++ty] = 1; ys[++ty] = b+1; 
        vs[++tv] = m;
        for(int i = 1; i <= n; ++i)
        {
            x1[i] = read(), y1[i] = read();
            x2[i] = read(), y2[i] = read();
            v[i] = read(); vs[++tv] = v[i]; vs[++tv] = v[i]-1;
            xs[++tx] = x1[i]; xs[++tx] = x2[i]+1; // 左闭右开
            ys[++ty] = y1[i]; ys[++ty] = y2[i]+1;
        }
        sort(xs+1, xs+1+tx); sort(ys+1, ys+1+ty); sort(vs+1, vs+1+tv);
        tx = unique(xs+1, xs+1+tx)-xs-1;
        ty = unique(ys+1, ys+1+ty)-ys-1;
        tv = unique(vs+1, vs+1+tv)-vs-1;         
        for(int i = 1; i < tx; ++i)
            for(int j = 1; j < ty; ++j)   
                w[i][j] = (xs[i+1]-xs[i])*(ys[j+1]-ys[j]); 
        for(int i = 1; i <= n; ++i)
        {
            x1[i] = lower_bound(xs+1, xs+1+tx, x1[i])-xs;
            y1[i] = lower_bound(ys+1, ys+1+ty, y1[i])-ys;
            x2[i] = lower_bound(xs+1, xs+1+tx, x2[i]+1)-xs;
            y2[i] = lower_bound(ys+1, ys+1+ty, y2[i]+1)-ys;
            v[i] = lower_bound(vs+1, vs+1+tv, v[i])-vs;       
        }        
        for(int s = 0; s < 1<<n; ++s)
        {
            int f = 1;
            for(int i = 1; i < tx; ++i)
                for(int j = 1; j < ty; ++j)
                    fv[i][j] = tv;
            for(int i = 1; i <= n; ++i)
            {
                int cv = v[i];
                if(s>>(i-1)&1) f = P-f, --cv;
                for(int j = x1[i]; j < x2[i]; ++j)
                    for(int k = y1[i]; k < y2[i]; ++k)
                        fv[j][k] = min(cv, fv[j][k]); 
            }
            for(int i = 1; i <= tv; ++i) c[i] = 0;
            for(int i = 1; i < tx; ++i)
                for(int j = 1; j < ty; ++j)
                    c[fv[i][j]] += w[i][j];
            int ret = 1;
            for(int i = 1; i <= tv; ++i) ret = 1ll*ret*qpow(vs[i], c[i])%P;
            ans = (ans+1ll*f*ret%P)%P;   
        }
        printf("%d\n", ans);
    }
    return 0;
}