感谢@似水流年 翻译

题意:

你有个h*w的矩阵

每个点的值在[1,m]之间

有n个要求(n<=10),每个要求在一个x1,y1-x2,y2的矩形内,其最大值是val(各个val值不同)

求方案数

解法:

离散化+容斥

RT....

离散化:h,w<=20(需要快速幂)

然后2^n暴力每个点是否满足<=val(或者val-1)的情况,容斥计算方案

然后..

因为之前写的快速幂所以TLE了..要写个优化..

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<math.h>
#include<string>
#include<time.h>
#include<bitset>
#include<vector>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<fstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define y1 fengqinhuaying
int mapx[10005];
int mapy[10005];
int tx[105],ty[105];
int x1[15],y1[15],x2[15],y2[15],val[15];
const int modo=1000000007;
int n,m;
int final_ans=0;
int k,p;
int sum[25][25];
int powers[25][25][2];
int std_sum[25][25];
inline int power(int x,int y)
{
    if (y==0) return 1;
    int t=power(x,y/2);
    t=(long long)t*t%modo;
    if (y&1) t=(long long)t*x%modo;
    return t;
}
void try_cal(int x)
{
    int i;
    for (i=0;i<n;i++)
    {
        int j;
        for (j=0;j<m;j++)
        {
            sum[i][j]=k;
        }
    }
    int flag=1;
    for (i=0;i<p;i++)
    {
        int j,l;
        if ((1<<i)&x) val[i]--;
        for (j=mapx[x1[i]];j<mapx[x2[i]];j++)
        {
            for (l=mapy[y1[i]];l<mapy[y2[i]];l++)
            {
                sum[j][l]=min(sum[j][l],val[i]);
            }
        }
        if ((1<<i)&x) val[i]++;
        if ((1<<i)&x) flag*=-1;
    }
    for (i=0;i<n;i++)
    {
        int j;
        for (j=0;j<m;j++)
        {
            flag=(long long)flag*powers[i][j][std_sum[i][j]-sum[i][j]]%modo;
        }
    }
    final_ans=(final_ans+flag)%modo;
}
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int t;
    scanf("%d",&t);
    int zu;
    for (zu=0;zu<t;zu++)
    {
        printf("Case #%d: ",zu+1);
        int nn,mm;
        scanf("%d%d%d%d",&nn,&mm,&k,&p);
        int i;
        for (i=0;i<p;i++)
        {
            scanf("%d%d%d%d%d",&x1[i],&y1[i],&x2[i],&y2[i],&val[i]);
            x1[i]--;
            y1[i]--;
            tx[i]=x1[i];
            tx[i+p]=x2[i];
            ty[i]=y1[i];
            ty[i+p]=y2[i];
        }
        tx[p+p]=0;
        tx[p+p+1]=nn;
        ty[p+p]=0;
        ty[p+p+1]=mm;
        sort(tx,tx+p+p+2);
        sort(ty,ty+p+p+2);
        n=unique(tx,tx+p+p+2)-tx-1;
        m=unique(ty,ty+p+p+2)-ty-1;
        for (i=0;i<=n;i++)
        {
            mapx[tx[i]]=i;
        }
        for (i=0;i<=m;i++)
        {
            mapy[ty[i]]=i;
        }
        try_cal(0);
        for (i=0;i<n;i++)
        {
            int j;
            for (j=0;j<m;j++)
            {
                powers[i][j][0]=power(sum[i][j],(tx[i+1]-tx[i])*(ty[j+1]-ty[j]));
                powers[i][j][1]=power(sum[i][j]-1,(tx[i+1]-tx[i])*(ty[j+1]-ty[j]));
                std_sum[i][j]=sum[i][j];
            }
        }
        final_ans=0;
        for (i=0;i<(1<<p);i++)
        {
            try_cal(i);
        }
        final_ans=(final_ans+modo)%modo;
        printf("%d\n",final_ans);
    }
    return 0;
}