容斥基本形式
∣
U
∩
A
1
‾
∩
A
2
‾
∩
⋯
∩
A
n
‾
∣
=
∑
S
⊆
A
(
−
1
)
∣
S
∣
∣
U
∩
S
1
∩
S
2
∩
⋯
∩
S
∣
S
∣
∣
\mathrm{|U\cap\overline{A_1}\cap\overline{A_2}\cap\cdots\cap\overline{A_n}|=\sum\limits_{S\subseteq A}(-1)^{|S|}|U\cap S_1\cap S_2\cap\cdots\cap S_{|S|}|}
∣U∩A1∩A2∩⋯∩An∣=S⊆A∑(−1)∣S∣∣U∩S1∩S2∩⋯∩S∣S∣∣
反演基本形式
f
n
=
∑
i
=
0
n
a
n
i
g
i
⇔
g
n
=
∑
i
=
0
n
b
n
i
f
i
f_n=\sum\limits_{i=0}^na_{ni}g_i\Leftrightarrow g_n=\sum\limits_{i=0}^nb_{ni}f_i
fn=i=0∑nanigi⇔gn=i=0∑nbnifi
也可以说是：
F
=
A
G
⇔
G
=
B
F
\mathbf F=\mathbf{AG}\Leftrightarrow \mathbf G=\mathbf{BF}
F=AG⇔G=BF 。则
B
=
A
−
1
=
A
∗
∣
A
∣
\mathbf B=\mathbf A^{-1} = \dfrac{\mathbf A^*}{|\mathbf A|}
B=A−1=∣A∣A∗ 。
（矩阵求逆暴力一点可以用高斯消元，把
[
A
∣
E
]
[\mathbf{A|E}]
[A∣E] 变成
[
E
∣
B
]
[\mathbf{E|B}]
[E∣B] 。不过反演一般不会这么搞）
反演成立的充要条件
∑
j
=
i
n
a
n
j
b
j
i
=
[
i
=
j
]
\sum\limits_{j=i}^na_{nj}b_{ji}=[i=j]
j=i∑nanjbji=[i=j]
二项式定理
(
a
+
b
)
n
=
∑
r
=
0
n
(
n
r
)
a
i
b
n
−
r
(a+b)^n=\sum\limits_{r=0}^n{n\choose r}a^ib^{n-r}
(a+b)n=r=0∑n(rn)aibn−r
二项式反演
g
n
=
∑
i
=
0
n
(
−
1
)
i
(
n
i
)
f
i
⇔
f
n
=
∑
i
=
0
n
(
−
1
)
i
(
n
i
)
g
i
g_n=\sum\limits_{i=0}^n(-1)^i{n\choose i}f_i\Leftrightarrow f_n=\sum\limits_{i=0}^n(-1)^i{n\choose i}g_i
gn=i=0∑n(−1)i(in)fi⇔fn=i=0∑n(−1)i(in)gi
至多↔恰好
g
n
=
∑
i
=
0
n
(
n
i
)
f
i
⇔
f
n
=
∑
i
=
0
n
(
−
1
)
n
−
i
(
n
i
)
g
i
g_n=\sum\limits_{i=0}^n{n\choose i}f_i\Leftrightarrow f_n=\sum\limits_{i=0}^n(-1)^{n-i}{n\choose i}g_i
gn=i=0∑n(in)fi⇔fn=i=0∑n(−1)n−i(in)gi
至少↔恰好
g
i
=
∑
j
=
i
n
(
j
i
)
f
j
⇔
f
i
=
∑
j
=
i
n
(
−
1
)
j
−
i
(
j
i
)
g
j
g_i=\sum\limits_{j=i}^n{j\choose i}f_j\Leftrightarrow f_i=\sum\limits_{j=i}^n(-1)^{j-i}{j\choose i}g_j
gi=j=i∑n(ij)fj⇔fi=j=i∑n(−1)j−i(ij)gj
一个套路：由
g
n
=
∑
i
=
0
n
−
1
(
n
i
)
f
i
+
f
n
g_n=\sum\limits_{i=0}^{n-1}{n\choose i}f_i+f_n
gn=i=0∑n−1(in)fi+fn 得到
f
n
=
g
n
−
∑
i
=
0
n
−
1
(
n
i
)
f
i
f_n=g_n-\sum\limits_{i=0}^{n-1}{n\choose i}f_i
fn=gn−i=0∑n−1(in)fi 就可以用
g
g
g 推
f
f
f 。
如果继续拆就可以由原式推出反演。
f
n
=
g
n
−
(
n
n
−
1
)
f
n
−
1
−
∑
i
=
0
n
−
2
(
n
i
)
f
i
f_n=g_n-{n\choose n-1}f_{n-1}-\sum\limits_{i=0}^{n-2}{n\choose i}f_i
fn=gn−(n−1n)fn−1−i=0∑n−2(in)fi
f
n
=
g
n
−
(
n
n
−
1
)
g
n
−
1
+
(
n
n
−
1
)
∑
i
=
0
n
−
2
(
n
−
1
i
)
f
i
−
∑
i
=
0
n
−
2
(
n
i
)
f
i
f_n=g_n-{n\choose n-1}g_{n-1}+{n\choose n-1}\sum\limits_{i=0}^{n-2}{n-1\choose i}f_i-\sum\limits_{i=0}^{n-2}{n\choose i}f_{i}
fn=gn−(n−1n)gn−1+(n−1n)i=0∑n−2(in−1)fi−i=0∑n−2(in)fi
f
n
=
g
n
−
(
n
n
−
1
)
g
n
−
1
+
∑
i
=
0
n
−
2
[
(
n
n
−
1
)
(
n
−
1
i
)
f
i
−
(
n
i
)
f
i
]
f_n=g_n-{n\choose n-1}g_{n-1}+\sum\limits_{i=0}^{n-2}\left[{n\choose n-1}{n-1\choose i}f_i-{n\choose i}f_i\right]
fn=gn−(n−1n)gn−1+i=0∑n−2[(n−1n)(in−1)fi−(in)fi]
f
n
=
g
n
−
(
n
n
−
1
)
g
n
−
1
+
∑
i
=
0
n
−
2
[
(
n
i
)
(
n
−
i
n
−
1
−
i
)
f
i
−
(
n
i
)
f
i
]
f_n=g_n-{n\choose n-1}g_{n-1}+\sum\limits_{i=0}^{n-2}\left[{n\choose i}{n-i\choose n-1-i}f_i-{n\choose i}f_i\right]
fn=gn−(n−1n)gn−1+i=0∑n−2[(in)(n−1−in−i)fi−(in)fi]
f
n
=
g
n
−
(
n
n
−
1
)
g
n
−
1
+
∑
i
=
0
n
−
2
(
n
i
)
(
n
−
i
−
1
)
f
i
f_n=g_n-{n\choose n-1}g_{n-1}+\sum\limits_{i=0}^{n-2}{n\choose i}(n-i-1)f_i
fn=gn−(n−1n)gn−1+i=0∑n−2(in)(n−i−1)fi
f
n
=
g
n
−
(
n
n
−
1
)
g
n
−
1
+
(
n
n
−
2
)
g
n
−
2
−
∑
i
=
0
n
−
3
(
n
−
2
i
)
f
i
+
∑
i
=
0
n
−
3
(
n
i
)
(
n
−
i
−
1
)
f
i
f_n=g_n-{n\choose n-1}g_{n-1}+{n\choose n-2}g_{n-2}-\sum\limits_{i=0}^{n-3}{n-2\choose i}f_i+\sum\limits_{i=0}^{n-3}{n\choose i}(n-i-1)f_i
fn=gn−(n−1n)gn−1+(n−2n)gn−2−i=0∑n−3(in−2)fi+i=0∑n−3(in)(n−i−1)fi
一直展开下去，猜想会得到
f
n
=
∑
i
=
0
n
(
−
1
)
n
−
i
(
n
i
)
g
i
f_n=\sum\limits_{i=0}^n(-1)^{n-i}{n\choose i}g_i
fn=i=0∑n(−1)n−i(in)gi 。证明一下，的确是。
遇到新的反演就可以这么推试试看（相信应该还有更好的方法，但是我实在找不到了）
不嫌麻烦的话说不定可以手模矩阵求逆，但是风险还比较大（（
二项式反演是组合数形式的容斥。
在集合
U
\mathrm U
U 中，有
n
n
n 个具有不同性质元素的集合
A
1
,
A
2
,
⋯
 
,
A
n
\mathrm{A_1,A_2,\cdots,A_n}
A1,A2,⋯,An
考虑容斥的特殊情况：集族
Q
=
{
A
1
,
A
2
,
⋯
 
,
A
n
}
\mathrm{Q=\{A_1,A_2,\cdots,A_n\}}
Q={A1,A2,⋯,An} 中任意
i
i
i 个集合的并集大小为
g
i
g_i
gi 。
那么
g
i
=
∣
A
1
∩
A
2
∩
⋯
∩
A
i
∣
g_i=\mathrm{|A_1\cap A_2\cap\cdots\cap A_i|}
gi=∣A1∩A2∩⋯∩Ai∣ ，在
Q
\mathrm Q
Q 中有
(
n
i
)
n\choose i
(in) 个这样的不同交集。定义
g
0
=
∣
U
∣
g_0=|\mathrm U|
g0=∣U∣ 。
由容斥原理有
∣
A
1
‾
∩
A
2
‾
∩
⋯
∩
A
n
‾
∣
=
∣
U
∣
−
∑
S
⊆
A
(
−
1
)
∣
S
∣
∣
S
1
∩
S
2
∩
⋯
∩
S
∣
S
∣
∣
\mathrm{|\overline{A_1}\cap\overline{A_2}\cap\cdots\cap\overline{A_n}|=|U|-\sum\limits_{S\subseteq A}(-1)^{|S|}|S_1\cap S_2\cap\cdots\cap S_{|S|}|}
∣A1∩A2∩⋯∩An∣=∣U∣−S⊆A∑(−1)∣S∣∣S1∩S2∩⋯∩S∣S∣∣
f
n
=
∣
A
1
‾
∩
A
2
‾
∩
⋯
∩
A
n
‾
∣
=
∑
i
=
0
n
(
−
1
)
i
(
n
i
)
g
i
f_n=\mathrm{|\overline{A_1}\cap\overline{A_2}\cap\cdots\cap\overline{A_n}|=}\sum\limits_{i=0}^n(-1)^i{n\choose i}g_i
fn=∣A1∩A2∩⋯∩An∣=i=0∑n(−1)i(in)gi
定义
f
i
=
∣
A
1
‾
∩
A
2
‾
∩
⋯
∩
A
i
‾
∣
f_i=\mathrm{|\overline{A_1}\cap\overline{A_2}\cap\cdots\cap\overline{A_i}|}
fi=∣A1∩A2∩⋯∩Ai∣ ，
f
0
=
∣
U
∣
f_0=|\mathrm U|
f0=∣U∣ ，有
g
n
=
∣
A
1
∩
A
2
∩
⋯
∩
A
n
∣
=
∑
i
=
0
n
(
−
1
)
i
(
n
i
)
f
i
g_n=\mathrm{|A_1\cap A_2\cap\cdots\cap A_n|=}\sum\limits_{i=0}^n(-1)^i{n\choose i}f_i
gn=∣A1∩A2∩⋯∩An∣=i=0∑n(−1)i(in)fi
首先为了方便把两个数组分别从小到大排序。
假设计数时的某种情况下糖果
a
i
a_i
ai ，药片
b
j
b_{j}
bj 。
i
,
j
≤
n
i,j\le n
i,j≤n 。
题目要求计数的是
∑
i
=
1
n
[
a
i
>
b
i
]
=
∑
i
=
1
n
[
b
i
>
a
i
]
+
k
\sum\limits_{i=1}^n[a_i>b_i]=\sum\limits_{i=1}^n[b_i>a_i]+k
i=1∑n[ai>bi]=i=1∑n[bi>ai]+k 的情况数。
想容斥：固定前面的一部分，然后后面的一部分容斥。
考虑安排
b
i
>
a
i
b_i>a_i
bi>ai 一类的，可以对每个
a
i
a_i
ai 预处理
b
j
b_j
bj 到哪里为止都小于
a
i
a_i
ai ，存为
s
i
s_{i}
si 。
安排的时候固定
a
a
a 和
b
b
b 中的一组，只拿另一组去配对 。
前面一部分可以算：到
i
i
i 为止，配对了
j
j
j 对
a
x
>
b
x
a_x>b_x
ax>bx （
x
≤
i
x\le i
x≤i）的方案数
t
i
,
j
t_{i,j}
ti,j 。
（没有配对的部分啥都没有）
有
t
i
,
j
=
t
i
−
1
,
j
+
[
g
i
>
j
−
1
]
[
(
s
i
−
j
+
1
)
t
i
−
1
,
j
−
1
]
t_{i,j}=t_{i-1,j}+[g_i>j-1][(s_i-j+1)t_{i-1,j-1}]
ti,j=ti−1,j+[gi>j−1][(si−j+1)ti−1,j−1] 。
到
n
n
n 为止， 至少 有
i
i
i 对
a
x
>
b
x
a_x>b_x
ax>bx 的方案数
（这个表述可能听起来有点奇怪，从 dp 式子观察，它实际上是指已知
i
i
i 对剩下的瞎排）
（所以说是这么说，实际上跟意义不相符的是它会重复计数。。。）
（稍微思考一下就知道了。）
，设为
f
i
f_{i}
fi ，有
f
i
=
t
n
,
i
(
n
−
i
)
!
f_{i}=t_{n,i}(n-i)!
fi=tn,i(n−i)! 。
“ 至少 ” 容易求，考虑二项式反演。把原问题转化成求：
到
n
n
n 为止， 恰好 有
n
+
k
2
\frac{n+k}{2}
2n+k 对
a
x
>
b
x
a_x>b_x
ax>bx 的方案数。（
n
+
k
n+k
n+k 为奇数要讨论）
要知道答案，首先要知道到 n n n 为止 恰好 有 i i i 对 a x > b x a_x>b_x ax>bx 的方案数。设为 g i g_{i} gi 。
考虑一下
g
j
g_j
gj 和
f
i
f_i
fi 的关系 （
i
≤
j
≤
n
i\le j\le n
i≤j≤n）。
g
j
g_j
gj 可能会在
f
i
f_i
fi 里面被多算。算了几次？
g
j
g_j
gj 有
j
j
j 对
a
x
>
b
x
a_x>b_x
ax>bx ；
t
n
,
i
t_{n,i}
tn,i 要求包含
i
i
i 对
a
x
>
b
x
a_x>b_x
ax>bx 。
j
j
j 对里面选
i
i
i 对，那么
g
j
g_j
gj 对
f
i
f_i
fi 的贡献就是
(
j
i
)
j\choose i
(ij) 。
按照减去多算的部分的思路， g i = f i − ∑ j = i + 1 n ( j i ) g j g_i=f_i-\sum\limits_{j=i+1}^n{j\choose i}g_j gi=fi−j=i+1∑n(ij)gj 。
如果考虑到
f
i
=
∑
j
=
i
n
(
j
i
)
g
j
f_i=\sum\limits_{j=i}^n{j\choose i}g_j
fi=j=i∑n(ij)gj 就可以二项式反演
g
i
=
∑
j
=
i
n
(
−
1
)
j
−
i
(
j
i
)
f
j
g_i=\sum\limits_{j=i}^n(-1)^{j-i}{j\choose i}f_j
gi=j=i∑n(−1)j−i(ij)fj 。
不知道也可以做，把
g
i
g_i
gi 从和号里面拆出来，稍作变换得
g
i
=
f
i
−
∑
j
=
i
+
1
n
(
j
i
)
g
j
g_i=f_i-\sum\limits_{j=i+1}^n{j\choose i}g_j
gi=fi−j=i+1∑n(ij)gj 。
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cctype>
#include <cmath>
using namespace std;
const long long MOD = 1000000009ll;
int n, k, m;
long long a[2005], b[2005];
long long c[2005][2005], f[2005], p[2005];
#define adjust(x) (x>=MOD)?(x-MOD):x
int main() {
scanf("%d%d", &n, &k);
if (n + k & 1) return printf("0"), 0;
for (register int i = 1; i <= n; ++i) scanf("%lld", &a[i]);
for (register int i = 1; i <= n; ++i) scanf("%lld", &b[i]);
for (register int i = 0, j; i <= n; ++i) {
for (j = 1, c[i][0] = 1; j <= i; ++j) {
c[i][j] = adjust(c[i-1][j-1] + c[i-1][j]);
}
}
p[0] = 1ll;
for (register int i = 1; i <= n; ++i) {
p[i] = 1ll * i * p[i-1] % MOD;
}
sort(a+1, a+1+n);
sort(b+1, b+1+n);
f[0] = 1ll;
for (register int z = 1, i = 1, j; i <= n; ++i) {
while (z <= n && a[i] > b[z]) ++z;
for (--z, j = i; j >= 1; --j) {
f[j] = (f[j] + f[j - 1] * max(0, z - j + 1)) % MOD;
}
}
m = n + k >> 1;
for (register int i = n; i >= m; --i) {
f[i] = f[i] * p[n - i] % MOD;
for (register int j = i + 1; j <= n; ++j) {
f[i] = (f[i] - c[j][i] * f[j] % MOD + MOD) % MOD;
}
}
printf("%lld",f[m]);
return 0;
}
因篇幅问题不能全部显示，请点此查看更多更全内容