优加优智OJ系统 主页 问题 问题分类 模拟竞赛
登录 注册

1385: 矩阵填数

内存限制：5 MB 时间限制：1.000 S 标准输入输出
题目类型：传统 评测方式：文本比较 上传者：
提交：0 通过：0
提交提交记录统计

题目描述

    给定一个h×w的矩阵，矩阵的行编号从上到下依次为1∼h，列编号从左到右依次1∼w。
    在这个矩阵中你需要在每个格子中填入1∼m中的某个数。
    给这个矩阵填数的时候有一些限制，给定n个该矩阵的子矩阵，以及该子矩阵的最大值v，要求你所填的方案满足该子矩阵的最大值为v。
    现在，你的任务是求出有多少种填数的方案满足n个限制。
    两种方案是不一样的当且仅当两个方案至少存在一个格子上有不同的数。由于答案可能很大，你只需要输出答案mod 1000000007。

输入格式

    输入数据的第一行为一个数 T，表示数据组数。
    对于每组数据，第一行为四个数h,w,m,n。
    接下来n行，每一行描述一个子矩阵的最大值v。
    每行为五个整数x1,y1,x2,y2,v，表示一个左上角为(x1,y1)，右下角为(x2,y2)的子矩阵的最大值为v，其中1≤x1≤x2≤h，1≤y1≤y2≤w。

输出格式

    对于每组数据输出一行，表示填数方案 mod 1000000007后的值。

输入样例 复制 

2 
3 3 2 2 
1 1 2 2 2 
2 2 3 3 1 
4 4 4 4 
1 1 2 3 3 
2 3 4 4 2 
2 1 4 3 2 
1 2 3 4 4

输出样例 复制 

28 
76475

数据范围与提示

    数据规模及约定：
    对于20%的数据：n≤2。
    另有20%的数据：1≤h,w≤50。  
    对于100%的数据：T≤5，1≤h,w,m≤10000，1≤v≤m，1≤n≤10。

分类标签

提交提交记录统计