题目描述
Chess Championship is set up in the New Basyuki City. Two national teams, of Berland and Byteland, are going to have a match there. Each team is represented by $n$ players. The championship consists of $n$ games – in each game a pair of players from different teams meets. A game victory brings $1$ point to the team and a game defeat doesn’t add or subtract points.
The championship starts with the sortition – the process that determines opponent pairs. Each player from the first team plays with exactly one player from the second team (and vice versa).
A recent research conducted by Berland scientists showed that every player of either team is characterized by a single number – the level of his chess mastership. No two people among the $2n$ players play at the same level. Funny as it is, the game winner always is the player with the higher level.
The contest organizers received information that a high-ranking Berland official Mr. B. bet $100500$ burles on the victory of his team with a $k$ points gap. Immediately an unofficial “recommendation” came from very important people to “organize” the sortition so that the Berland team gets exactly $k$ points more than the Byteland team.
Write a program that finds the number of distinct sortition results after which Berland gets exactly $k$ points more than Byteland. Two sortitions are considered distinct if there is such player, that gets different opponents by the sortitions’ results.
题意概述
给定两组数$a_i, b_i$，每组$n$个数。保证所有$a_i, b_i$中不会出现相同的数。求有多少个排列$p$满足$\sum_{i=1}^n [a_i \gt b_{p_i}]-\sum_{i=1}^n [a_i \lt b_{p_i}]=k$。
数据范围：$1 \le k \le n \le 500$。
算法分析
当$k \not \equiv n \pmod 2$时，排列不存在。
将所有数从小到大排序。令$f_{i, j, k}$表示在前$i$个数中，有$j$个$a$中的数匹配了$b$中比它小的数，有$k$个$b$中的数匹配了$a$中比它小的数的方案数。转移时只要计算前$i$个数中两组分别有几个数未匹配，枚举第$i$个数是否匹配另一组中比它小的数。最后的答案就是$f_{2n, {n+k \over 2}, {n-k \over 2}}$。
需要滚动数组。
代码
#include <algorithm>
#include <cstdio>
#include <cstring>
static int const N = 505;
static int const MOD = 1000000009;
int f[2][N][N];
std::pair<int, int> a[N << 1];
int main() {
int n, k;
scanf("%d%d", &n, &k);
if ((n & 1) != (k & 1))
return puts("0"), 0;
for (int i = 0; i < n; ++i)
scanf("%d", &a[i].first);
for (int i = n; i < n << 1; ++i)
scanf("%d", &a[i].first), a[i].second = 1;
std::sort(a, a + (n << 1));
int cur = 0, s[2] = {0, 0};
f[0][0][0] = 1;
for (int i = 0; i < n << 1; ++i, cur ^= 1) {
for (int j = 0; j <= n; ++j)
for (int k = 0; j + k <= n; ++k)
if (f[cur][j][k]) {
(f[!cur][j][k] += f[cur][j][k]) %= MOD;
int c[2] = {s[0] - j - k, s[1] - j - k};
(f[!cur][j + !a[i].second][k + a[i].second] += 1ll * f[cur][j][k] * c[!a[i].second] % MOD) %= MOD;
f[cur][j][k] = 0;
}
++s[a[i].second];
}
printf("%d\n", f[cur][n + k >> 1][n - k >> 1]);
return 0;
}