BZOJ3622 已经没有什么好害怕的了

时间:2022-09-03 00:04:49

Description

BZOJ3622 已经没有什么好害怕的了

Input

BZOJ3622 已经没有什么好害怕的了

Output

BZOJ3622 已经没有什么好害怕的了

Sample Input

4 2
5 35 15 45
40 20 10 30

Sample Output

4

HINT

BZOJ3622 已经没有什么好害怕的了

输入的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 }