有两个长度为n的排列A和B，定义排列的价值f(A,B)为所有满足A[i]>B[i]的位置i的数量。
现给出n，A，B和S，其中A和B中有一些位置的数未知，问有多少种可能的填数的方案使得f(A,B)=S
保证不存在一个位置i满足A[i]=0且B[i]=0
十分有趣的题目，是个神奇的组合数学+dp
我们先将问题拆成两个，因为题目保证没有A[i]=B[i]=0的位置
我们将所有A[i]=0的B[i]取出来，将这些元素排序得到x
再将所有不在A中的元素取出来排序得到y，设长度为m
那么，我们设一个dp
f[i][j]表示已经做到第i个数，其中已经保证有j个位置有贡献，其余位置情况不清楚的方案数
那么f[i][j]=f[i-1][j]+f[i-1][j-1]*(k-j){ k是满足x[k-1]<y[i]的最大的k }
我们令g[j]表示f[m][j]*(m-j)! 这样就得到了最终的方案数（因为对于其余位置不清楚的情况，可以随意调换位置）
我们现在可以用容斥原理来计算贡献恰好为j的g'[j]，那么显然g'[m]=g[m]
让后可以得到g'[j]=g[j]-Σg'[i]*C(j,i) {j<i<=m} 倒序计算即可
让后类似的我们可以将B[i]=0的A[i]取出来做一次类似的dp，也求出一个g''
那么答案就是Σg'[i]*g''[i-s](0<=i<=S)
感觉讲的比较不清楚，可以好好理解一下
（十月份都是什么题啊！！！！！！！）
#pragma GCC optimize("O3")
#pragma G++ optimize("O3")
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define N 4010
#define LL long long
#define M 1000000007
using namespace std;
bool va[N],vb[N];
int a[N],b[N],n,m,s,x[N],y[N];
LL js[N],inv[N],f[N],g[N],Answer=0;
inline LL C(int n,int m){ return js[n]*inv[m]%M*inv[n-m]%M; }
inline LL pow(LL x,int k,LL S=1){
for(;k;x=x*x%M,k>>=1) if(k&1) S=S*x%M;
return S;
}
int main(){
freopen("arrange.in","r",stdin);
freopen("arrange.out","w",stdout);
scanf("%d%d",&n,&s);
for(int i=*js=*inv=1;i<=n;++i) js[i]=js[i-1]*i%M;
for(inv[n]=pow(js[n],M-2);;) break;
for(int i=n;i;--i) inv[i-1]=inv[i]*i%M;
for(int i=1;i<=n;++i){
scanf("%d",a+i);
va[a[i]]=1;
}
for(int i=1;i<=n;++i){
scanf("%d",b+i);
vb[b[i]]=1;
if(a[i]&&b[i]&&a[i]>b[i]) --s;
}
m=0;
for(int i=1;i<=n;++i) if(!a[i]) x[++m]=b[i];
sort(x+1,x+1+m); m=0;
for(int i=1;i<=n;++i) if(!va[i]) y[++m]=i;
f[0]=1;
for(int i=1,k=1;i<=m;++i){
for(;k<=m && y[i]>x[k];++k);
for(int j=i;j;--j) f[j]=(f[j]+f[j-1]*(k-j))%M;
}
for(int i=m;~i;--i){
f[i]=(f[i]*js[m-i])%M;
for(int j=i+1;j<=m;++j) f[i]=(f[i]+M-f[j]*C(j,i)%M)%M;
}
m=0;
for(int i=1;i<=n;++i) if(!b[i]) x[++m]=a[i];
sort(x+1,x+1+m); m=0;
for(int i=1;i<=n;++i) if(!vb[i]) y[++m]=i;
for(int i=1;i<=m;++i) swap(x[i],y[i]);
g[0]=1;
for(int i=1,k=1;i<=m;++i){
for(;k<=m && y[i]>x[k];++k);
for(int j=i;j;--j) g[j]=(g[j]+g[j-1]*(k-j))%M;
}
for(int i=m;~i;--i){
g[i]=(g[i]*js[m-i])%M;
for(int j=i+1;j<=m;++j) g[i]=(g[i]+M-g[j]*C(j,i)%M)%M;
}
for(int i=0;i<=s;++i) Answer=(Answer+f[i]*g[s-i]%M)%M;
printf("%lld
",Answer);
}