LINK

题意：给出n,k，有a,b两种值，a和b间互相配对，求$a>b$的配对组数-b>a的配对组数恰好等于k的情况有多少种。

思路：粗看会想这是道容斥组合题，但关键在于如何得到每个a[i]大于b的组数。

不妨从整体去考虑，使用$f[n][j]$代表前n个中有j组$a[i]>b[i]$，很容易得到转移式$f[n][j]=f[n-1][j]+f[n-1][j-1]*(cnt[n]-(j-1))$，其中$cnt[i]$为比a[i]小的b[]个数

但是仔细思考该式子含义会发现，$f[n][j]$得到的是不小于j组满足a[i]>b[]的数，会造成大于j组数情况的重复计入

我们定义$dp[n][i]$代表选取i组恰好糖果大于药片的方案 也就是正确答案

那么实际上总情况有$dp[n][i] = f[n][i]*(n-i)! $即剩下n-i个数自由配对 有$(n-i)!$种

重复情况为任意选取大于i(i+1~n)的 并在其中无序选出i个的种类数 即 $\sum^{n}_{j=i+1}{dp[n][i]*C(j,i)}$

/** @Date    : 2017-07-17 16:15:38  * @FileName: bzoj 3622 DP + 容斥.cpp  * @Platform: Windows  * @Author  : Lweleth (SoungEarlf@gmail.com)  * @Link    : https://github.com/  * @Version : $Id$  */#include <stdio.h>#include <iostream>#include <string.h>#include <algorithm>#include <utility>#include <vector>#include <map>#include <set>#include <string>#include <stack>#include <queue>#include <math.h>//#include <bits/stdc++.h>#define LL long long#define PII pair<int ,int>#define MP(x, y) make_pair((x),(y))#define fi first#define se second#define PB(x) push_back((x))#define MMG(x) memset((x), -1,sizeof(x))#define MMF(x) memset((x),0,sizeof(x))#define MMI(x) memset((x), INF, sizeof(x))using namespace std;const int INF = 0x3f3f3f3f;const int N = 1e5+20;const double eps = 1e-8;const LL mod = 1e9 + 9;LL a[2100];LL b[2100];LL dp[2100];LL f[2100][2100];LL fac[2100];LL inv[2100];LL cnt[2100];int n, k;void init(){	fac[0] = fac[1] = 1;	inv[0] = inv[1] = 1;	for(int i = 2; i <= 2010; i++)	{		fac[i] = fac[i - 1] * i % mod;		inv[i] = (mod - mod / i) * inv[mod % i] % mod;	}	for(int i = 2; i <= 2010; i++)		(inv[i] *= inv[i - 1]) %= mod;}LL C(int n, int m){	LL ans = 0;	if(m > n)		return ans;	ans = ((fac[n] * inv[m]) % mod * inv[n - m]) % mod;	return ans;}int main(){	while(cin >> n >> k)	{		init();		LL m = (n + k) / 2;		for(int i = 1; i <= n; i++) scanf("%lld", a + i);		for(int i = 1; i <= n; i++) scanf("%lld", b + i);		sort(a + 1, a + n + 1);		sort(b + 1, b + n + 1);		for(int i = 1; i <= n; i++)		{			for(int j = 1; j <= n; j++)				if(a[i] > b[j])					cnt[i] = j;		}		for(int i = 0; i <= n; i++)		{			f[i][0] = 1;			for(int j = 1; j <= i; j++)			{				f[i][j] = f[i - 1][j];				if(cnt[i] - (j - 1) > 0)					f[i][j] += f[i - 1][j - 1] * (cnt[i] - (j - 1));				f[i][j] %= mod;			}		}		for(int i = n; i >= m; i--)		{			dp[i] = f[n][i] * fac[n - i] % mod;			for(int j = i + 1; j <= n; j++)			{				dp[i] = (dp[i] - dp[j] * C(j, i) % mod + mod) % mod;			}		}		printf("%lld\n", dp[m]);	}    return 0;}

bzoj 3622 DP + 容斥