Chess Championship

题目描述

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;
}