「题目描述」

史蒂夫想在minecraft里盖一座房子，众所周知，minecraft世界主要是由各式各样的立方体组成的。

可惜的是，现在史蒂夫只拿到了建筑图纸的左视图和正视图（如下所示）。请问可能有多少种建筑符合给定的左视图和正视图，答案对10^9 + 9取模。方块不能悬空摆放。

「输入格式」

第一行一个整数n，表示正视图的列数。

第二行n个整数，表示每列能看到的最高的立方体柱的高度。

第三行一个整数m，表示左视图的列数。

第四行m个整数，表示每列能看到的最高的立方体柱的高度。

「输出格式」

一个整数表示答案。

「样例输入」

2

1 1

2

1 1

「样例输出」

7

「数据范围」

对于10%的数据，1 <= n,m <= 5；

对于30%的数据，1 <= n,m <= 10；

对于60%的数据，1 <= n,m <= 25；

对于100%的数据，1 <= n,m <= 50，所有出现的数不超过10^4。

题解

给定一个矩阵每行每列的最大值

求矩阵填数方案

蒟蒻只yy出30分。。。

将每一行/列是否有已有最大值状压

然后枚举每个格子填数

复杂度n^2 2^n

搬运coolinging神犇学长的题解

易得本题中左视图和正视图中数字的顺序是独立的，故可将两行数字排序后处理。

左/正视图中的第i个数字h限制了俯视图中第i行/列的所有格子不超过高度h，且至少有一格高度为h。

第i行第j列的数字的最大值为d[i][j] = min(左视图第i个数字, 正视图第j个数字)，即数字范围是[0, d[i][j]]。若将两行数字从小到大排序后，d[i][j]相同的数字会形成一个个L型。易于发现，d[i][j]不同的格子之间是互不影响的。

现在问题简化为求每个L型的填放方案数，设数字的取值范围为[0, h]。“每行/列至少有一个高度为h的格子”的反面是“每行/每列所有格子高度<h”，后者显然比前者好统计（即数字范围为[0,h-1]，方案数=h^格子数）。

故采用容斥法求解，先无视每行每列至少有一高度为h的格子这一限制条件，求出一个总方案数，再减去非法的方案数。求解非法的方案数时，枚举共有i行j列不满足条件（使用组合数学求得非法行列的取法总数）,则其余行列满足条件。注意其余行列同样构成一个L型，故转化为了子问题，使用动态规划解决。

时间复杂度O((nm)^2 * (n+m))

30分

100待填坑