bzoj 3622 DP + 容斥

题意：给出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 + 容斥

最新文章

热门文章