题目描述
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; }