Description
让我们来考虑一个单位立方体建成的模型。这个建筑的底是一个n m的单位正方形网格。在每个正方形上面，堆着若干个（可能是0）个单位立方体。每个立方体属于其中一个立方体堆。 给出了一个建筑的左视图和正视图。请计算有多少种建筑，符合给出的左视图和正视图。答案可能很大，只要返回它除以10^9 + 9的余数即可。
Input
第一行是整数n。第二行描述了建筑的左视图。第i个数表示了由上往下看时第i行最高的立方体堆的高度。第三行是整数m。第四行描述了建筑的正视图。第i个数表示了由上往下看时第i列最高的立方体堆的高度。
Output
仅一个数，表示答案。
Sample Input
2 1 1 2 1 1
Sample Output
7
Data Constraint
对于10%的数据，1<= n,m <= 5。 对于30%的数据，1 <= n,m <=10。 对于60%的数据，1 <= n,m <= 25。 对于100%的数据，1 <= n,m <= 50，所有出现的数不超过10^4。
解法：首先，有一个很重要的结论：我们将左视图的一些值交换，主视图不变；我们将主视图的一些值交换，左视图不变。因此，我们可以先将主和左视都从小到大排序
1.
2
排序后，我们可以看到若干个L形区域（如图1），每个L形中的格子允许填的最大值相同。我们可以对于每个"L"分开处理，最后将答案乘起来
对于每个"L"，我们可以用dp处理，每一个L（如图2）需满足：
1.每个格的值不超过h,
2.前h1行和前enoughsize列都需满足每行/列至少有1个h
我们设dp状态f[i][j]表示填到第i行，前enoughsize列已有j列满足有h的方案，
转移时，我们枚举下一行要新满足多少列，f[i][j]乘的系数为C(enoughsize-j,k)*h^(enoughsize-j-k)（只满足k个，剩下的不能填h）*(h+1)^(cur（当前行长度）-enoughsize+j)
注意如果是前h1行需满足至少有一个h，因些当k=0时我们要减去一个h都没有的方案，即h^cur
即f[i+1][j+k]+=f[i][j]*xs(上述系数)
End.
#include#include #include #include #include using namespace std;typedef long long ll;class AxonometricProjection{public: int howManyWays(vector ,vector );};int f[101][101];int U[10011],D[10011],L[10011],R[10011];int pra[10011],prb[10011],a[10011],b[10011];int c[101][101];int ans,n,m,i,j;int mo=1000000009;int mi(int x,int z){ int l; l=1; while(z){ if(z%2==1)l=(ll)l*x%mo; x=(ll)x*x%mo; z/=2; } return l;}int calc(int h1,int h2,int en,int ful,int h){ int i,j,k,ts,cur; memset(f,0,sizeof(f)); f[0][0]=1; for(i=0;i