首先 \(ai>bi\) 的有 \(\frac{n+k}{2}\) 组 将a,b排序 设 \(f[i][j]\) 表示前\(i\)个,至少有\(j\)组满足(\(ai>bi\)) 的方案数 求出满足 \(a[i]>b[k]\) 的最大的\(k\)\(f[i][j]=f[i-1][j]+f[i-1][j-1]*(k-(j-1))\) 最后容斥一下 \(ans=\sum_{i=k}^{n}(-1)^{i-k}*f[n][i]*c[i][k]*(n-i)!\)
#include<bits/stdc++.h> using namespace std; const int N=2010,mod=1e9+9; int n,K,a[N],b[N],g[N],f[N][N],c[N][N],bin[N]; int main(){ freopen("pp.in","r",stdin); freopen("pp.out","w",stdout); scanf("%d%d",&n,&K); if((n+K)&1)puts("0"),exit(0); else K=(n+K)>>1; for(int i=1;i<=n;i++)scanf("%d",&a[i]); for(int i=1;i<=n;i++)scanf("%d",&b[i]); sort(a+1,a+n+1);sort(b+1,b+n+1); for(int i=1;i<=n;i++)g[i]=lower_bound(b+1,b+n+1,a[i])-b-1; for(int i=0;i<=n;i++){ f[i][0]=1;c[i][0]=1; for(int j=1;j<=i;j++) f[i][j]=(f[i-1][j]+1ll*f[i-1][j-1]*(g[i]-j+1))%mod, c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod; } int ans=0; bin[0]=1;for(int i=1;i<=n;i++)bin[i]=1ll*bin[i-1]*i%mod; for(int i=K;i<=n;i++) ans=(ans+1ll*((i-K)&1?-1:1)*f[n][i]*bin[n-i]%mod*c[i][K])%mod; if(ans<0)ans+=mod; cout<<ans<<endl; return 0; }转载于:https://www.cnblogs.com/Yuzao/p/8438208.html
相关资源：数据结构—成绩单生成器