4 2 5 35 15 45 40 20 10 30
4
输入的2*n个数字保证全不相同。
还有输入应该是第二行是糖果，第三行是药片
容斥原理好题。 另外这题面……
思路: 首先将糖果数组 a 和药片数组b分别排好序。
直接算太困难，考虑使用容斥原理简化一下约束。 预处理一个数组 c[i] 表示 b 中比a[i]小的数的个数。 考虑dp，令 f[i][j] 表示考虑到第 i 个a，已经选出了 j 对(x,y)满足 a[x]>b[y] 的方案数。 转移方程很简单，可以滚动数组加速:
f[i][j]=(f[i−1][j]+f[i−1][j−1]∗max(0,c[i]−j+1)
可以发现， f[n][j]∗(n−j)! 恰好为至少有 j 组(x,y)满足 a[x]>b[y] 的方案数。 令 g[i] 为恰好有 i 组(x,y)满足 a[x]>b[y] 的方案数，同时下面采用 f[i] 代替 f[n][i]∗(n−i)! 。 那么， g[j] 恰好在 f[i] 中被算了 (ji) 次。
于是有以下式子: f[i]=∑nj=i(ji)∗g[j] 考虑二项式反演: g[i]=∑nj=i(−1)j−i∗(ji)∗f[j]
此时， g[(n+k)/2] 便是最终答案。 完成~
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> using namespace std; typedef long long ll; const int N=2009; const int md=1e9+9; inline int read() { int x=0;char ch=getchar(); while(ch<'0' || '9'<ch)ch=getchar(); while('0'<=ch && ch<='9')x=x*10+(ch^48),ch=getchar(); return x; } int n,k,a[N],b[N],c[N]; ll f[2][N],fac[N],inv[N]; inline ll qpow(ll a,ll b) { ll ret=1; while(b) { if(b&1) ret=ret*a%md; a=a*a%md; b>>=1; } return ret; } inline ll co(ll a,ll b){return fac[a]*inv[b]%md*inv[a-b]%md;} inline ll maxx(ll a,ll b){if(a>b)return a;return b;} inline ll chk(ll &a){if(a>=md)a-=md;} int main() { n=read();k=read(); for(int i=1;i<=n;i++) a[i]=read(); for(int i=1;i<=n;i++) b[i]=read(); sort(a+1,a+n+1); sort(b+1,b+n+1); for(int i=1,j=0;i<=n;i++,c[i]=c[i-1]) while(c[i]<n && b[c[i]+1]<a[i])c[i]++; f[0][0]=1; for(int i=1;i<=n;i++) for(int j=0;j<=c[i];j++) chk(f[i&1][j]=(f[i&1^1][j]+f[i&1^1][j-1]*maxx(0,(ll)c[i]-j+1ll)%md)); fac[0]=1; for(ll i=1;i<=n;i++) fac[i]=fac[i-1]*i%md; inv[n]=qpow(fac[n],md-2); for(ll i=n;i>=1;i--) inv[i-1]=inv[i]*i%md; int s=(n+k)>>1; ll ans=0; for(int i=s;i<=n;i++) (ans+=((i-s)&1?(md-1):1)*co(i,s)%md*f[n&1][i]%md*fac[n-i]%md)%=md; printf("%lld\n",ans); return 0; }