# 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.

## 代码

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


418 I'm a teapot