题面描述
给定集合 \(A\) 和 \(B\)，求完全匹配满足 \(\sum[a_i>b_i]-[a_i\le b_i]=k\)
的方案数
题解
首先，题意即是要求匹配满足 \(\sum[a_i>b_i]=\frac{n+k}{2}\)
的方案数，假设状态 \(h_{i,j}\) 表示前
\(i\) 个 匹配满足 \(\sum[a_k>b_k]=j\) 的方案数
考虑转移的顺序，发现对于当前决策\(a_k>b_k\)而言，必须考虑当前状态下有多少满足的
\(b_k\)，这就要求我们一开始把两者排序，则当前符合决策的
\(b_k\) 必定有 \(j\) 个已选，即有转移
\[
h_{i,j}\ =\ h_{i-1,j}+h_{i-1,j-1}\times(less_i-(j-1))
\] 我们发现对于 \(h_{n,k}\)
而言，我们得出并不是合法方案，因为中间放弃匹配的 \(a\) 最后必须匹配，所以 \(h_{n,k}\times(n-k)!\) 就是至少选出 \(k\) 个匹配的方案数
不妨设 \(f_k\) 为恰好为 \(k\) 组的方案数，\(g_k\) 为至少为 \(k\) 组的方案数，注意到 \(f_i\) 与 \(f_j\) 表示的集合无交集，发现 \(f\) 和 \(g\) 正好满足
\[
g_k\ =\ \sum_{i=k}^n\binom{i}{k}f_k
\]
根据二项式反演
\[
f_k\ =\ \sum_{i=k}^n(-1)^{i-k}\binom{i}{k}g_k
\]
最后求解即可
实际上这就是广义容斥的至少到恰好的运用
若有集合 \(S_1\)，\(S_2\)，\(S_3\)， ... \(S_n\) 和指标集 \(\mathcal{I}\)，和作用于指标集的函数 \(f\) 和 \(g\) 有
\[
f(I)\ =\ |\bigcap_{\alpha\in I}S_{\alpha}-\bigcup_{\alpha\notin
I}S_{\alpha}|
\]
即 \(f(I)\) 满足元素恰好在指标集
\(I\)
所代表的集合的交中，而不在其他不属于 \(I\) 的集合中
\[
g(I)\ =\ |\bigcap_{\alpha\in I}S_{\alpha}|
\]
即 \(g(I)\) 满足至少在指标集 \(I\) 的元素个数
\[
g(I)\ =\ \sum_{I\subseteq J}f(J)
\]
则有
\[
f(I)\ =\ \sum_{I\subseteq J}(-1)^{|J|-|I|}g(J)
\]
而在这道题的对于我们就是把 \(S_i\)
表示 \(a_i\) 的所配对的 \(b_i\) 有 \(a_i>b_i\)，在这个意义下使用广义容斥罢了
特别的，假如说对于 \(|I|\)
一定的子集的贡献可以统一起来用组合数计算贡献时，广义容斥即派生出组合广义容斥
此外，对于
\[
g(I)\ =\ |\bigcup_{\alpha\in I}S_{\alpha}-\bigcup_{\alpha\notin
I}S_{\alpha}|
\]
\(g(I)\) 表示至多在指标集 \(I\) 的元素个数，有
\[
g(I)\ =\ \sum_{J\subseteq I}f(J)
\] \[
f(I)\ =\ \sum_{J\subseteq I}(-1)^{|I|-|J|}g(J)
\]
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
46
47
48
49
50
51
52
| #include <cstdio>
#include <algorithm>
#include <cctype>
#include <cstring>
using namespace std;
inline int read(int f = 1, int x = 0, char ch = ' ')
{
while(!isdigit(ch = getchar())) if(ch == '-') f = -1;
while(isdigit(ch)) x = x*10+ch-'0', ch = getchar();
return f*x;
}
const int N = 2e3+5, P = 1e9+9;
int qpow(int a, int b)
{
int ret = 1;
for( ; b; b >>= 1, a = 1ll*a*a%P) if(b&1) ret = 1ll*ret*a%P;
return ret;
}
int n, k, a[N], b[N];
int h[N][N], f[N], g[N], res[N];
int fac[N], ifac[N];
int C(int n, int m) { return 1ll*fac[n]*ifac[n-m]%P*ifac[m]%P; }
int main()
{
n = read(), k = read(); fac[0] = ifac[0] = 1;
if((n+k)&1) return puts("0"), 0; k = (n+k)/2;
for(int i = 1; i <= n; ++i) a[i] = read();
for(int i = 1; i <= n; ++i) b[i] = read();
for(int i = 1; i <= n; ++i) fac[i] = 1ll*fac[i-1]*i%P;
ifac[n] = qpow(fac[n], P-2);
for(int i = n-1; i; --i) ifac[i] = 1ll*ifac[i+1]*(i+1)%P;
sort(a+1, a+1+n); sort(b+1, b+1+n);
for(int i = 1, p = 0; i <= n; ++i)
{
for( ; p < n&&b[p+1] < a[i]; ++p);
res[i] = p;
}
h[0][0] = 1;
for(int i = 1; i <= n; ++i)
{
h[i][0] = h[i-1][0];
for(int j = 1; j <= i; ++j)
h[i][j] = (h[i-1][j]+1ll*h[i-1][j-1]*max(0, res[i]-j+1)%P)%P;
}
for(int i = 0; i <= n; ++i) g[i] = 1ll*h[n][i]*fac[n-i]%P;
for(int i = k; i <= n; ++i)
if((i-k)&1) f[k] = (f[k]+P-1ll*C(i, k)*g[i]%P)%P;
else f[k] = (f[k]+1ll*C(i, k)*g[i]%P)%P;
printf("%d\n", f[k]);
return 0;
}
|