只会打暴力系列
首先应该是容斥，但行和列都需要考虑不知如何容
所以设法确定列，然后容斥行
先有一个结论：把 \(A, B\) 排序对答案不产生影响
所以我们先把 \(A, B\) 从大到小排序，然后从大到小枚举在 \(A, B\) 中出现过的数
可以发现每个这样的数确定了一个 \(L\) 形的范围的max
分别容斥每个数对应的 \(L\) 形区域，令 \(f_i\) 为至少有 \(i\) 行不满足约束的方案数，\(s\) 为这个数
先考虑最左上角的 \(a*b\) 的矩形
对着柿子还挺好理解的
- 求一个数列/矩阵中最大值恰好为 \(s\) 的方案数： \(ans = s^{siz}-s^{siz-1}\)
然后推广到 \(L\) 形：
发现因为是从大到小，\(L\) 的两个旋臂已经被解除限制了，只考虑拐角处的矩形就好
那相应的柿子就是
对 \(f\) 进行容斥，最后把每个 \(s\) 对应的答案乘起来就好
Code:
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define N 100010
#define ll long long
#define reg register int
//#define int long long
char buf[1<<21], *p1=buf, *p2=buf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf, 1, 1<<21, stdin)), p1==p2?EOF:*p1++)
inline int read() {
int ans=0, f=1; char c=getchar();
while (!isdigit(c)) {if (c=='-') f=-f; c=getchar();}
while (isdigit(c)) {ans=(ans<<3)+(ans<<1)+(c^48); c=getchar();}
return ans*f;
}
int n;
int a[N], b[N];
const ll mod=1e9+7;
namespace force{
int mp[10][10], t[N], ans;
bool check() {
memset(t, 0, sizeof(int)*(n+5));
for (int j=1; j<=n; ++j)
for (int i=1; i<=n; ++i)
t[j]=max(t[j], mp[i][j]);
for (int i=1; i<=n; ++i) if (t[i]!=a[i]) return 0;
memset(t, 0, sizeof(int)*(n+5));
for (int i=1; i<=n; ++i)
for (int j=1; j<=n; ++j)
t[i]=max(t[i], mp[i][j]);
for (int i=1; i<=n; ++i) if (t[i]!=b[i]) return 0;
return 1;
}
void dfs(int i, int j) {
if (j>n) {j=1; ++i;}
if (i>n) {if (check()) ++ans; return ;}
int lim=min(b[i], a[j]);
for (int k=0; k<=lim; ++k) {
mp[i][j]=k;
dfs(i, j+1);
}
}
void solve() {
dfs(1, 1);
printf("%d\n", ans);
exit(0);
}
}
namespace task{
ll fac[N], inv[N];
ll qpow(ll a, int b) {ll ans=1ll; for (; b; a=a*a%mod, b>>=1) if (b&1) ans=ans*a%mod; return ans;}
inline ll C(int n, int k) {return fac[n]*inv[k]%mod*inv[n-k]%mod;}
inline int cmp(int a, int b) {return a>b;}
void solve() {
ll ans=1, tem=0;
sort(a+1, a+n+1, cmp);
sort(b+1, b+n+1, cmp);
if (a[1]!=b[1]) {puts("0"); exit(0);}
fac[0]=fac[1]=1; inv[0]=inv[1]=1;
for (int i=2; i<=n; ++i) fac[i]=fac[i-1]*i%mod;
for (int i=2; i<=n; ++i) inv[i]=(mod-mod/i)*inv[mod%i]%mod;
for (int i=2; i<=n; ++i) inv[i]=inv[i-1]*inv[i]%mod;
for (int pos1=0,pos2=0,c=0,d=0,s=a[1]; pos1<=n||pos2<=n; c=0,d=0,tem=0) {
while (1) {
if (pos1<n && b[pos1+1]==s) ++pos1, ++c;
else if (pos2<n && a[pos2+1]==s) ++pos2, ++d;
else break;
}
for (int i=0,f=1; i<=c; ++i,f=-f) {
//cout<<"i: "<<i<<endl;
tem = ( tem + 1ll*f * C(c, i) * qpow(qpow(s, i)*qpow(s+1, c-i)%mod, pos2-d)%mod * qpow(qpow(s, i)*(((qpow(s+1, pos1-i)-qpow(s, pos1-i))%mod+mod)%mod)%mod, d)%mod )%mod;
}
//cout<<"L: "<<s<<' '<<pos1<<' '<<pos2<<' '<<c<<' '<<d<<' '<<tem<<endl;
ans = ans*tem%mod;
if (pos1==n && pos2==n) break;
s=max(pos1<n?b[pos1+1]:0, pos2<n?a[pos2+1]:0);
}
printf("%lld\n", (ans%mod+mod)%mod);
exit(0);
}
}
signed main()
{
n=read();
for (int i=1; i<=n; ++i) a[i]=read();
for (int i=1; i<=n; ++i) b[i]=read();
//force::solve();
task::solve();
return 0;
}