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也不用求。

#include <cstdio>
#include <algorithm>
using namespace std;
const int mod = 1000000009;
int n, k, ans, a[2010], b[2010], C[2010][2010], mul[2010], f[2010][2010];
main() {
    scanf("%d%d", &n, &k);
    if ((n + k) & 1)
        return 0, puts("0");
    k = (n + k) / 2; f[0][0] = 1;
    C[0][0] = C[1][0] = 1;
    for (int i = 1; i <= 2000; ++i, C[i][0] = 1)
        for (int j = 1; j <= i; ++j)
            C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
    mul[0]=1;
    for (int i = 1; i <= n; ++i) mul[i] = 1ll * mul[i - 1] * i % mod;
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    for (int i = 1; i <= n; ++i) scanf("%d", &b[i]);
    sort(a + 1, a + 1 + n), sort(b + 1, b + 1 + n);
    for (int i = 0, p = 0; i <= n; ++i) {
        while (b[p + 1] < a[i + 1] && p < n) ++p;
        for (int j = 0; j <= i; ++j)
            if (f[i][j] != 0) {
                f[i + 1][j] = (f[i + 1][j] + f[i][j]) % mod;
                if (p - j >= 0)
                    f[i + 1][j + 1] = (f[i + 1][j + 1] + 1ll * f[i][j] * (p - j) % mod) % mod;
            }
    }
    for (int i = 0; i <= n; ++i) f[n][i] = 1ll * f[n][i] * mul[n - i] % mod;
    for (int i = k, dlt = 1; i <= n; ++i, dlt = -dlt)
        ans = (ans + 1ll * dlt * C[i][k] * f[n][i] % mod) % mod;
    ans = (ans + mod) % mod;
    printf("%d\n",ans);
}