二项式反演 - 组合数学 | Bzw's Blog = Bzw = my Blog

若

$g_n = \sum_{i=0}^n\dbinom{n}{i}f_n$

有

$f_n=\sum_{i=1}^{n}\dbinom{n}{i}g_n$

若

$g_i=\sum_{j=i}^{n} \dbinom{j}{i}f_j$

则

$f_i=\sum_{j=i}^{n}\dbinom{j}{i}(-1)^{j-i}g_j$

P4859 已经没有什么好害怕的了

给两个数列 $a$ , $b$ , 要求 $a_i,b_i$ 两两匹配，使得 $a_i>b_i$ 的个数减去 $a_i<b_i$ 的个数等于 $k$ ，求总方案数。

先将 $a,b$ 排序，定义 $f_{i,j}$ 为前 $i$ 个 $a[i]$ 中恰好有 $j$ 个满足 $a_i>b_i$ 的方案数，其他的均未匹配的方案数。

有 $f_{i,j} = f_{i-1,j} + f_{i-1,j-1}(r_i-(j-1))$ 。

其中 $r_i$ 为 $b$ 中小于 $a_i$ 的个数。

定义 $g_i$ 为满足 $a_j>b_j$ 的个数大于 $i$ 的方案数， $G_i$ 表示满足 $a_j>b_j$ 的个数等于 $i$ 的方案数。

可以发现 $G_i$ 在 $g_j$ （ $i>j$ ）中出现了 $\tbinom{i}{j}$ 次。

有

$g_i=f_{n,i}(n-i)!$

$g_i = \sum_{j=i}^{n}\dbinom{j}{i}G_j$

$G_i = \sum_{j=i}^{n}\dbinom{j}{i}(-1)^{j-i}g_j$

	#include <bits/stdc++.h>
	using namespace std;
	using ll = long long;
	inline ll Max(ll x, ll y){return x > y ? x : y;}
	const ll N = 2001;
	const ll mod = 1e9 + 9;
	ll n, c[N][N], f[N][N], g[N], a[N], b[N], mx[N], fac[N];
	void init_c(ll tt){
	c[0][0]=1;
	for(ll i = 1; i <= tt; i++){
	c[i][0]=1;
	for(ll j = 1; j <= tt; j++)
	c[i][j] = (c[i-1][j] + c[i-1][j-1]) % mod;
	}
	}
	void init_fac(ll tt){
	fac[0] = 1;
	for(ll i = 1; i <= tt; i++)
	fac[i] = fac[i-1] * i % mod;
	}
	ll fu(ll x){return x&1?-1:1;}
	int main(){
	ll k;
	cin>>n>>k;
	for(ll i = 1; i <= n; i++)
	cin >> a[i];
	for(ll i = 1; i <= n; i++)
	cin >> b[i];
	sort(a+1, a+n+1);
	sort(b+1, b+n+1);
	init_c(n);
	init_fac(n);
	f[0][0]=1;
	for(ll i = 1; i <= n; i++){
	mx[i] = lower_bound(b+1, b+n+1, a[i]) - b - 1;
	f[i][0] = f[i-1][0];
	for(ll j = 1; j <= i; j++)
	f[i][j] = (f[i-1][j] + f[i-1][j-1] * Max(0, (mx[i] - j + 1)) % mod) % mod;
	}
	ll x = (n + k) >> 1;
	if((n+k)%2)cout<<0<<endl, exit(0);
	ll ans = 0;
	for(ll i = x; i <= n; i++)
	ans = (ans + fu(i-x) * c[i][x] % mod * f[n][i] % mod * fac[n-i] % mod) % mod;
	cout << (ans % mod + mod) % mod << endl;
	return 0;
	}