luogu2159(DP+容斥)

|

题目链接

https://www.luogu.org/problem/P2159

题解

这里发现求大于 $j$ 的方案数是比较好求的

设 $d[i][j]$ 为到 $i$ 时限定 $j$ 个女生大于男生，其余随意的方案数

这里 $cnt$ 为身高小于 $i$ 女生的男生数

这里会发现方案数是被计重的，设最后的 $DP$ 值为 $f[k]$ ，正好有 $k$ 个女生大于男生的方案数为 $g[k]$ ，则

那么根据二项式反演得到

这个式子也可以用容斥意义得到


另外一个方法是依次求出 $g$ ，即

倒着求解就可以了。。




代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
n,m=map(int,input().split())
a=[0]
b=[0]
for i in range(n):
    b.append(int(input()))
for i in range(n):
    a.append(int(input()))
a=sorted(a)
b=sorted(b)
d=[0]*(n+1)
d[0]=1
cnt=0
for i in range(1,n+1):
    while cnt<=n and a[i]>b[cnt]:
        cnt+=1
    for j in range(i,0,-1):
        if cnt-j>0:
	        d[j]+=d[j-1]*(cnt-j)

p=[1]
for i in range(n):
    p.append(p[i]*(i+1))

for i in range(n+1):
    d[i]=d[i]*p[n-i]


c=[[0]*(n+1) for i in range(n+1)]
c[0][0]=1
for i in range(n):
    for j in range(i+1):
        c[i+1][j]+=c[i][j]
        c[i+1][j+1]+=c[i][j]

f=[0]*(n+1)
for i in range(0,n+1):
    for j in range(i,n+1):
        if (j-i)&1:
            f[i]-=d[j]*c[j][i]
        else:
            f[i]+=d[j]*c[j][i]
ans=0
for i in range(0,m+1):
    ans+=f[i]
print(ans)