BZOJ3622（容斥+dp）

思路

“恰k个”考虑求至少k、k+1……个容斥
题面说所有数字都不同，可以将所求转化为糖比药多的组数恰为$(n+k)/2$的方案数
$f[i][j]$数组我觉得更好的理解方式是"前i个已经安排了j组糖大于药、别的先没管"的方案数
$f[n][i]*(n-i)!$即为把其它的安排了以后的方案数，但是这里面有重的
设$g[i]$为恰i个的方案数。$$g[i]=f[n][i]*(n-i)!-\sum_{j=i+1}^ng[j]*C_ji$$要说为什么又去重又剪掉不合法了，我也不通透，目前只是已知这样做是对的话那直观感受一下应该对吧……

#include <cstdio>

#include <algorithm>

using namespace std;

typedef long long ll;

const int mod = 1e9 + 9;

const int maxn = 2005;

int n, k, m, ans;

int a[maxn], b[maxn];

ll f[maxn][maxn], g[maxn];

ll fac[maxn], C[maxn][maxn];

int READ() {

	scanf("%d %d", &n, &k);

	for (int i = 1; i <= n; i++)

		scanf("%d", &a[i]);

	for (int i = 1; i <= n; i++)

		scanf("%d", &b[i]);

	m = (n + k) / 2;

	return (n + k) % 2;

}

void PRE() {

	sort(a + 1, a + 1 + n);

	sort(b + 1, b + 1 + n);

	fac[0] = 1;

	for (int i = 1; i <= n; i++)

		fac[i] = fac[i - 1] * i % mod;

	for (int i = 0; i <= n; i++) {

		C[i][0] = 1;

		for (int j = 1; j <= i; j++)

			C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;

	}

}

void DP() {

	for (int i = 0; i <= n; i++)

		f[i][0] = 1;

	for (int i = 1, p = 0; i <= n; i++) {

		for (; p < n && b[p + 1] < a[i]; p++);

		for (int j = 1; j <= i; j++) {

			f[i][j] = (f[i - 1][j - 1] * max(0, p - j + 1) % mod + f[i - 1][j]) % mod;

		}

	}

	for (int i = n; i >= m; i--) {

		g[i] = f[n][i] * fac[n - i] % mod;

		for (int j = i + 1; j <= n; j++) {

			g[i] = (g[i] - g[j] * C[j][i] % mod) % mod;

		}

	}

	ans = (g[m] + mod) % mod;

}

int main() {

	if (READ() == 1) {

		return !printf("0\n");

	}

	PRE();

	DP();

	return !printf("%d\n", ans);

}

巴特西

BZOJ3622（容斥+dp）

思路

最新文章

热门文章