【题解】BZOJ 3622 已经没有什么好害怕的了

请注意,本文编写于 97 天前,最后修改于 97 天前,其中某些信息可能已经过时。

Flag 已立,凉凉

Problem

给定 $n$ 个糖果的权值 $a_i$ 和 $n$ 个药片的权值 $b_i$

求两两匹配后糖果比药片权值大的组数恰好比药片比糖果权值大的组数多 $k$ 组的方案数

Thought

设糖果比药片权值大的组数为 $x$ ,相应的另外一种情况为 $n-x$

那么需要使得 $x-(n-x)=k$ 即 $x=\frac{n+k}{2}$

设 $f(x)$ 表示糖果比药片权值大的组数为 $x$ 的方案数
设 $F(x)$ 为满足确定 $i$ 个糖果比药片权值大的组,其余任意匹配的方案数

使用 集合选数 中相同的思路,我们可以得出某一组匹配对两者的贡献关系,同样可以列出方程:

$$ F(k)=\sum_{i=0}^{n}{i\choose k}f(i) $$

如何求得 $F$ 呢?

考虑将 $a,b$ 从小到达排序,设 $g_{i,j}$ 表示当前匹配到 $a_i$ ,已经有 $j$ 组满足条件的匹配的方案数

我们同时维护一个值 $siz$,表示在 $a_i$ 时有多少个 $b$ 比 $a_i$ 小

转移显然: $g_{i,j}=g_{i-1,j}+g_{i-1,j-1}*(siz-(j-1))$

那么 $F(x)=g_{n,x}$
最后二项式反演一下求 $f(x)$

$$ f(k)=\sum_{i=0}^{n}(-1)^{|k-i|}{i\choose k}F(i) $$

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int read() {
    int ans = 0, flag = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
const int N = 2010;
const int mod = 1000000009;
int n, k;
int a[N], b[N];
int g[N][N], F[N];

int inv[N], invPro[N];
int fac[N];

void prepare() {
    inv[0] = invPro[0] = fac[0] = 1;
    inv[1] = invPro[1] = fac[1] = 1;
    for(int i = 2; i < N; ++ i) {
        inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;
        invPro[i] = 1ll * invPro[i - 1] * inv[i] % mod;
        fac[i] = 1ll * fac[i - 1] * i % mod;;
    }
}
int C(int n, int m) {
    if(n < m) return 0;
    return 1ll * fac[n] * invPro[m] % mod * invPro[n - m] % mod;
}
int qpow(int a, int b) {
    int ans = 1;
    while(b) {
        if(b & 1) ans = 1ll * ans * a % mod;
        a = 1ll * a * a % mod;
        b >>= 1;
    }
    return ans;
}
int main() {
    prepare();
    n = read(); k = read();
    for(int i = 1; i <= n; ++ i) a[i] = read();
    for(int i = 1; i <= n; ++ i) b[i] = read();
    sort(a + 1, a + n + 1);
    sort(b + 1, b + n + 1);
    int head = 1;
    g[0][0] = 1;
    int bigger = 0;
    for(int i = 1; i <= n; ++ i) {
        while(head <= n && a[i] > b[head]) {
            ++ bigger;
            ++ head;
        }
        for(int j = 0; j <= bigger; ++ j) {
            g[i][j] += g[i - 1][j];
            if(j) g[i][j] += 1ll * g[i - 1][j - 1] * (bigger - j + 1) % mod;
            g[i][j] %= mod;
        }
    }
    for(int i = 0; i <= n; ++ i)
        F[i] = 1ll * g[n][i] * fac[n - i] % mod;
    if((n + k) % 2) puts("0");
    else {
        k = (n + k) / 2;
        int ans = 0;
        for(int i = k; i <= n; ++ i) {
            if((k - i) % 2) {
                ans -= 1ll * C(i, k) * F[i] % mod;
                while(ans < 0) ans += mod; 
            }
            else {
                ans += 1ll * C(i, k) * F[i] % mod;
                while(ans >= mod) ans -= mod;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}
Comments

添加新评论