CF1946E Girl Permutation

中文题面：https://www.luogu.com.cn/problem/CF1946E

先考虑只要求前缀最大值怎么做。从前往后很容易想到\(O(n^3)\)的dp，用前缀和优化可以到\(O(n^2)\).注意相对顺序，\([p_i,p_{i+1}-1]\)选择的数，必须让最大的放在最前面才合法。比如选1,3,9,在[5,8]这个区间，只有9,1,3和9,3,1是合法的。从后往前考虑每一段，发现前面的选择对后面没有影响（相对顺序不变）。

后缀最大值考虑的方法类似。注意判断合法状态。a[m1] != b[1] || a[1] != 1 || b[m2] != n, 即最大值在前后缀相同，前缀第一个在1，后缀最后一个在n。

#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int mod = 1e9 + 7;
const int N = 2e5 + 11;
int a[N], b[N];
int n, m1, m2;
LL fac[N], invo[N], inv[N];
LL C(int n, int m){
  return fac[n] * inv[m] % mod * inv[n-m] % mod;
}
void work(){
  cin>>n>>m1>>m2;
  for(int i = 1;i <= m1; i++){
    scanf("%d", &a[i]);
  }
  for(int i = 1;i <= m2; i++){
    scanf("%d", &b[i]);
  }
  if(a[m1] != b[1] || a[1] != 1 || b[m2] != n){
    cout<<0<<endl;
    return ;
  }
  LL res = C(n - 1, a[m1] - 1);
  LL tmp = a[m1] - 1;
  for(int i = m1 - 1;i >= 1; i--){
    tmp--;
    res = res * C(tmp, a[i+1] - a[i] - 1) % mod * fac[a[i+1]-a[i]-1] % mod;
    tmp -= a[i+1] - a[i] - 1;
  }
  tmp = n - a[m1];
  for(int i = 1;i < m2; i++){
    tmp--;
    res = res * C(tmp, b[i+1] - b[i] - 1) % mod * fac[b[i+1]-b[i]-1] % mod;
    tmp -= b[i+1] - b[i] - 1;
  }
  cout<<res<<endl;
}
int main(){
  int T;
  cin>>T;
  fac[0] = fac[1] = inv[0] = inv[1] = 1;
  for(int i = 1;i <= 2e5; i++){
    fac[i] = 1ll * fac[i-1] * i % mod;
  }
  for(int i = 2;i <= 2e5; i++){
    inv[i] = (mod - mod / i) * inv[mod%i] % mod;
  }
  for(int i = 2;i <= 2e5; i++){
    invo[i] = inv[i];
    inv[i] = inv[i-1] * inv[i] % mod;
  }
  while(T--)work();
  return 0;
}