Description

有一个 的网格,在每个格子上堆叠了一些边长为 11 的立方体。

现在给出这个三维几何体的正视图和左视图,求有多少种与之符合的堆叠立方体的方案。两种方案被认为是不同的,当且仅当某个格子上立方体的数量不同。

输出答案对 109+710^{9} + 7 取模的结果。

Input

从文件 silhouette.in 中读入数据.
第一行一个整数 nn.
第二行 nn 个整数,第 ii 个表示正视图中从左到右第 ii 个位置的高度 AiA_{i}
第三行 nn 个整数,第 ii 个表示左视图中从左到右第 ii 个位置的高度 BiB_{i}

Output

输出到文件 silhouette.out 中.
输出一行表示答案。

Sample Input

2
1 2
2 1
3
3 1 3
2 3 2
3
1 1 1
3 3 3

Sample Output

5
175
0

数据范围

对于所有数据,有 .

Solution

题目实际是问下面的方程组有多少非负整数解:

i[1,n],maxj=1n{xi,j}=Ai,maxj=1n{xj,i}=Bi\forall i \in [1, n], \max_{j = 1}^n \{x_{i, j}\} = A_i, \max_{j = 1}^n \{x_{j, i}\} = B_i

显然,对一个已经成立的答案,交换一列或交换一行,只需要同时交换 AiA_{i}BiB_{i} ,那么答案等价。

如果 AA 的最大值不等于 BB 的最大值则答案是 00,否则一定有解。

不妨将 Ai,BiA_{i},B_{i} 按照从大到小排序,现在考虑使这个矩阵成立的方案数。

section 1

显然有 xi,jmin(Ai,Bj)x_{i, j} \le \min(A_i, B_j). 从大到小枚举每个 A,BA, B 中出现的值ss,每次确定所有 min(Ai,Bj)=s\min(A_i, B_j) = s 的位置的值。

我们先来考虑 ss 为最大值的情况,此时我们要确定的位置构成了一个矩形。可以发现我们要解决这样一个子问题:一个 a×ba \times b 的矩形,每个位置的值在 [0,s][0, s] 中,且每行每列的最大值均为 ss,需要计算有多少取值的方案。

这样求方案不好做,我们可以先保证每一列合法。不妨设 f(i)f(i) 为至少有 ii 行的限制不满足条件时的方案(需要保证每一列都满足条件)。这个方案很好算,只需要先取出 ii 行使其不满足条件,在剩下的行里选至少一个等于 ss 的数即可。即:

f(i)=(ai)(si×((s+1)aisai))bf(i) = {a \choose i} (s^i \times ((s+1)^{a - i} - s^{a - i}))^b

对其简单容斥,那么答案就是: i=0a(1)if(i)\sum_{i = 0}^a (-1)^i f(i)

section 2

若某时刻 Ai=BiA_{i}=B_{i},那么我们每次要确定的位置可能是一个L形,考虑将其拆成两个矩形容斥。 设矩形为 a×ba \times baa 的上面还有长为 cc 的边, bb 的左边还有长为 dd 的边。那么 f(i)f(i) 为:

f(i)=(ai)(si×((s+1)a+cisa+ci))b×(si×(s+1)ai)df(i) = {a \choose i} (s^i \times ((s+1)^{a+c - i} - s^{a+c - i}))^b \times (s^{i} \times (s+1)^{a-i})^{d}

时间复杂度 O(n log n)O(n~log~n) 。 好难啊。

Code

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
#include <bits/stdc++.h>
using namespace std;
#define re register int
#define rep(i,a,b) for(re i=a;i<=b;++i)
#define drep(i,a,b) for(re i=a;i>=b;--i)
#define _ 0
template <class T>inline void read(T &x) {
x=0; int f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
x*=f;
}

int n, a[100005], b[100005], ans=1;
int fac[100005], inv[100005];
#define p 1000000007

int qpow(int a,int b) {
int r=1;
for(;b;b>>=1,a=1ll*a*a%p)if(b&1) r=1ll*r*a%p;
return r;
}
int C(int n,int m) {return 1ll*fac[n]*inv[m]%p*inv[n-m]%p;}
inline void add(int &x) {if(x>=p)x-=p;}

signed main() {
read(n);
rep(i,1,n)read(a[i]); sort(a+1,a+n+1);
rep(i,1,n)read(b[i]); sort(b+1,b+n+1);
if(a[n]!=b[n]) return puts("0"),0; //GG

fac[0]=1; rep(i,1,n) fac[i]=1ll*fac[i-1]*i%p;
inv[n]=qpow(fac[n],p-2); drep(i,n-1,0) inv[i]=1ll*inv[i+1]*(i+1)%p;

int i=1, j=1, s=min(a[1],b[1]);
while(i<=n&&j<=n) {
int lena=0, lenb=0;
while(s==a[i]) ++lena,++i;
while(s==b[j]) ++lenb,++j;

int c=n-i+1, d=n-j+1, t, sum=0;
rep(z,0,lena) {
if(z&1) t=p-C(lena,z); else t=C(lena,z);
t = 1ll*t*qpow(1ll*qpow(s,z)*(qpow(s+1,c+lena-z)-qpow(s,c+lena-z)+p)%p, lenb)%p;
t = 1ll*t*qpow(1ll*qpow(s,z)*qpow(s+1,lena-z)%p, d)%p;
add(sum+=t);
}
add(sum+=p);
ans = 1ll*ans*sum%p;
s = min(a[i],b[j]);
}
printf("%d\n", ans);
return ~~(0^_^0);
}