Description
Input
Output
Sample Input
4 2
5 35 15 45
40 20 10 30
5 35 15 45
40 20 10 30
Sample Output
4
HINT
输入的2*n个数字保证全不相同。
还有输入应该是第二行是糖果,第三行是药片
首先$a_i>b_i$的情况数:
$k=\frac{n+k}{2}$
如果不能整除则无解
先按a,b排序
预处理出$l[i]$,表示$a_i$大于$b_j$的最大j
这样设f[i][j]表示当前a序列第i个数,有j组$a>b$的方案
使$a_i>b$有$l[i]$种方案,但是前面已经用了j-1
所以$f[i][j]=f[i-1][j]+f[i-1][j-1]*(l[i]-j+1)$
这样求出来的是“至少”有j对的方案数,而我们需要的是“恰好”有k对的方案数。
所以容斥
$ans=\sum_{i=k}^{n}(-1)^{i-k}*f[n][i]*C_i^{k}*(n-i)!$
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<algorithm>
5 #include<cmath>
6 using namespace std;
7 typedef long long lol;
8 int a[2001],b[2001],n,k,Mod=1e9+9,l[2001];
9 lol f[2001][2001],C[2001][2001],fac[2001],ans;
10 int main()
11 {int i,j;
12 cin>>n>>k;
13 if ((n+k)&1)
14 {
15 cout<<0;
16 return 0;
17 }
18 k=(n+k)/2;
19 fac[0]=1;
20 for (i=1;i<=n;i++)
21 fac[i]=1ll*fac[i-1]*i%Mod;
22 for (i=0;i<=n;i++)
23 {
24 C[i][0]=1;
25 for (j=1;j<=i;j++)
26 C[i][j]=(C[i-1][j-1]+C[i-1][j])%Mod;
27 }
28 for (i=1;i<=n;i++)
29 {
30 scanf("%d",&a[i]);
31 }
32 for (i=1;i<=n;i++)
33 {
34 scanf("%d",&b[i]);
35 }
36 sort(a+1,a+n+1);sort(b+1,b+n+1);
37 for (i=1;i<=n;i++)
38 {
39 for (j=1;j<=n;j++)
40 if (a[i]>b[j]) l[i]++;
41 else break;
42 }
43 for (i=0;i<=n;i++)
44 {
45 f[i][0]=1;
46 for (j=1;j<=i;j++)
47 {
48 f[i][j]=(f[i][j]+1ll*(l[i]-(j-1))*f[i-1][j-1]%Mod)%Mod;
49 f[i][j]=(f[i][j]+f[i-1][j])%Mod;
50 }
51 }
52 for (i=k;i<=n;i++)
53 {
54 if ((i-k)%2==0)
55 ans+=1ll*f[n][i]*C[i][k]%Mod*fac[n-i]%Mod,ans%=Mod;
56 else ans-=1ll*f[n][i]*C[i][k]%Mod*fac[n-i]%Mod,ans=(ans+Mod)%Mod;
57 }
58 cout<<ans;
59 }