Description
Input
Output
Sample Input
4 25 35 15 4540 20 10 30
Sample Output
4
HINT
输入的2*n个数字保证全不相同。
还有输入应该是第二行是糖果，第三行是药片
题解
前置知识 ：
首先很显然可以知道，题目要求的是要配对恰好\((n+k)/2\)个第一行比第二行大的方案数。
对于第一行和第二行从小到大分别排序下，
然后设\(f_{i,j}\)表示考虑到第一行第i个数了，有至少j个配对成功的方案数。
对于第一行的第i个数，设\(num_i\)表示第二行有多少个数小于它，
然后可以得到\(f\)的转移：
\[ f(i,j)=f(i-1,j)+f(i-1,j-1)*max(0,num_i-j+1) \] 然后考虑求恰好k个的方案数，考虑容斥，答案为：\[ \sum_{i=k}^n (-1)^{i-k} \binom{k}{i} f(n,i)*(n-i)! \]#includeusing namespace std; #define int long long void read(int &x) { x=0;int f=1;char ch=getchar(); for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f; for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;} void print(int x) { if(x<0) x=-x,putchar('-'); if(!x) return ;print(x/10),putchar(x%10+'0');}void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');} #define maxn 2050 const int mod = 1e9+9; int n,f[maxn][maxn],fac[maxn],ifac[maxn],k,num[maxn],a[maxn],b[maxn]; int qpow(int a,int x) { int res=1; for(;x;x>>=1,a=a*a%mod) if(x&1) res=res*a%mod; return res;} signed main() { read(n),read(k);fac[0]=ifac[0]=f[0][0]=1; if((n^k)&1) return puts("0"),0; k=(n+k)>>1; for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%mod; ifac[n]=qpow(fac[n],mod-2); for(int i=n-1;i;i--) ifac[i]=ifac[i+1]*(i+1)%mod;//,write(ifac[i]); for(int i=1;i<=n;i++) read(a[i]); for(int i=1;i<=n;i++) read(b[i]); sort(a+1,a+n+1),sort(b+1,b+n+1);int p=0; for(int i=1;i<=n;i++) { while(a[i]>b[p]&&p<=n) p++;p--;num[i]=p; }//for(int i=1;i<=n;i++) write(num[i]); for(int i=1;i<=n;i++) { f[i][0]=f[i-1][0]; for(int j=1;j<=i;j++) f[i][j]=(f[i-1][j]+f[i-1][j-1]*max(0ll,num[i]-j+1))%mod; } //for(int i=1;i<=n;i++) write(f[n][i]); int ans=0; for(int op=-1,i=k;i<=n;i++) { op=-op;//write(op*fac[i]*ifac[k]%mod*ifac[i-k]%mod); f[n][i]=f[n][i]*fac[n-i]%mod; ans=(ans+op*fac[i]*ifac[k]%mod*ifac[i-k]%mod*f[n][i]%mod)%mod; }write((ans%mod+mod)%mod); return 0;}