bzoj 3622 已经没有什么好害怕的了

Description

Input

Output

Sample Input

4 2

5 35 15 45

40 20 10 30

Sample Output

4

HINT

输入的2*n个数字保证全不相同。

还有输入应该是第二行是糖果，第三行是药片

题解

首先算一下应该有多少对$A_x > B_x$，发现$2x + k = n$，也就是$x = {n – k \over 2}$，那么$x + k = {n + k \over 2}$，那么$n + k \over 2$肯定要是个整数，所以可以先判下无解的情况。

现在的限制是很强的，要求恰好有k组，也就是说剩下的一定要是小于的情况。做这种容斥题就可以先考虑弱化它的限制，然后用容斥再满足它的限制。比如这种恰好k的就可以先dp出至少k的再容斥出来恰好的情况。

考虑一下至少k的怎么dp。$f[i][j]$表示A和B分别排序后，dp到了A组的第i个数字，A比B大的有j组。

这样的话因为两个数组都是有序的所以可以很方便地定位一段A比B大的前缀，设这段前缀一共有p个数，里面一开始已经选了j个，还剩下p-j个没有选，所以递推f[i+1]的时候就是：

$f[i][j] += f[i – 1][j]$（不限制第i个要大）
$f[i][j] += f[i – 1][j – 1] \times (p – j)$（限制第i个要大）

接下来就是容斥一下，设$g[i][j]$为有恰好j个小。我们发现对于一个$ f[i][j]$它的非确定A大于B的那些数对中，有$ (i−j)!$种排列。那么按照这种容斥

$$g[i][j]=f[i][j]\times (i−j)! − \sum_{k = j + 1}^n g[i][k] \times C^i_j$$

只要对于$i = n$的时候容斥一下就行了，g也不用求。