洛谷 P4859 && BZOJ3622: 已经没有什么好害怕的了

题目描述

给出 \(n\) 个数 \(a_i\) ，以及 \(n\) 个数 \(b_i\) ，要求两两配对使得 \(a>b\) 的对数减去 \(a<b\) 的对数等于 \(k\) 。

\(0≤k≤n≤2000\)，保证 \(a,b\) 无相同元素。

题解

我们假设 \(a>b\) 对数为 \(x\) ，可以求得 \(x=\frac{n+k}{2}\) 。

先对两个数组都排序

设\(pos[i]\)表示最大的\(j\)使得\(a_i>b_j\)

我们令 \(f_{i,j}\) 表示前 \(i\) 个 \(a\) 中，选了 \(j\) 组满足 \(a>b\) 的方案数。（注意不是前i个\(b\)）

\(f_{i,j}\) = \(f_{i-1, j-1} + f_{i-1, j-1} * (pos[i]-j+1)\)

然而，这样弄完后，我们会发现会发现计算中的方案可以选多余\(j\)组，这样就会算重复许多方案

考虑如何去重

设\(g[i]\)表示前i个a，恰好选了\(j\)组

\(g[i]=f[n][i]∗(n−i)!−∑g[j] * C_j^i, (i<j≤n)\)

因为不知道a里面剩下的\(n-i\)个数是怎么匹配的，但是一定有\((n−i)!\)种匹配情况，这些情况里包含了恰好有j组a大于b的情况\((i<j)\)，j组被计算到的次数是 \(C_j^i\) 种，所以减去，\(g[m]\)即是答案

Code

#include<bits/stdc++.h>

#define LL long long

#define RG register

using namespace std;

inline int gi() {

    int f = 1, s = 0;

    char c = getchar();

    while (c != '-' && (c < '0' || c > '9')) c = getchar();

    if (c == '-') f = -1, c = getchar();

    while (c >= '0' && c <= '9') s = s*10+c-'0', c = getchar();

    return f == 1 ? s : -s;

}

const int N = 2010, Mod = 1e9+9;

int a[N], b[N], pos[N];

LL jc[N], C[N][N], f[N][N], g[N];

int main() {

	int n = gi(), m = gi();

	if ((n+m)&1) {

		printf("0\n");

		return 0;

	}

	m = (n+m)>>1;

	for (int i = 1; i <= n; i++) a[i] = gi();

	for (int i = 1; i <= n; i++) b[i] = gi();

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

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

		int p = 0;

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

		pos[i] = p;

	}

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

		C[i][0] = 1;

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

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

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

	jc[0] = jc[1] = 1;

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

		jc[i] = jc[i-1]*i%Mod;

	f[0][0] = 1;

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

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

			if (pos[i] >= j)

				f[i][j] = (f[i-1][j] + f[i-1][j-1]*(pos[i]-j+1))%Mod;

		}

	}

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

		g[i] = f[n][i]*jc[n-i];

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

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

	}

	printf("%lld\n", g[m]);

    return 0;

}

巴特西

洛谷 P4859 && BZOJ3622: 已经没有什么好害怕的了

题目描述

题解

Code

最新文章

热门文章