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

Gena vs Petya

题目描述

Gena and Petya love playing the following game with each other. There are $n$ piles of stones, the $i$-th pile contains $a_i$ stones. The players move in turns, Gena moves first. A player moves by choosing any non-empty pile and taking an arbitrary positive number of stones from it. If the move is impossible (that is, all piles are empty), then the game finishes and the current player is considered a loser.
Gena and Petya are the world famous experts in unusual games. We will assume that they play optimally.
Recently Petya started to notice that Gena wins too often. Petya decided that the problem is the unjust rules as Gena always gets to move first! To even their chances, Petya decided to cheat and take and hide some stones before the game begins. Since Petya does not want Gena to suspect anything, he will take the same number of stones $x$ from each pile. This number $x$ can be an arbitrary non-negative integer, strictly less that the minimum of $a_i$ values.
Your task is to find the number of distinct numbers $x$ such that Petya will win the game.

题意概述

给定$n$个正整数$a_i$,求有多少个非负整数$x$,满足$x$小于所有给定的数,且所有给定的数减去$x$之后的异或和为$0$。
数据范围:$1 \le n \le 2 \times 10^5, \; 1 \le a_i \le 10^{18}$。

算法分析

Nim游戏后手胜利的条件是所有数的异或和为$0$。
枚举$x$显然不可行。可以尝试从低位到高位依次确定。
考虑低位对高位的影响,易知只有当低位退位时才会改变高位。而对于每一位,若此位上有偶数个$0$,则此位可以填$1$,若有偶数个$1$则可以填$0$(这样才能使得异或和为$0$)。
令$f_{i, j}$表示从低到高处理到第$i$位时,有$j$个数字在第$(i+1)$位退位的方案数。根据退位的性质,这$j$个数字一定是所有给定的数按后$i$位从小到大排序后的前$j$个。可以在枚举$i$的同时基数排序,枚举$j$的同时维护第$i$位上$0$和$1$的个数(会受退位影响),若满足条件则转移(注意此位填$1$时还要考虑此位$0$的退位)。
最后需要特判一下$x$不能等于所有给定的数中最小的数。

代码

#include <algorithm>
#include <cstdio>
#include <cstring>

#define int long long

static int const N = 200005;
static int const M = 65;
int a[N], cnt[M], f[M][N], s[2][N];

signed main() {
  int n;
  scanf("%lld", &n);
  for (int i = 0; i < n; ++i) {
    scanf("%lld", a + i);
    for (int j = 0; j < M; ++j)
      cnt[j] += a[i] >> j & 1;
  }
  f[0][0] = 1;
  for (int i = 0; i < M - 1; ++i) {
    int c0 = n - cnt[i], c1 = cnt[i], c = 0;
    for (int j = 0; j <= n; ++j) {
      if (j)
        if (a[j - 1] >> i & 1)
          ++c0, --c1;
        else
          --c0, ++c1, ++c;
      if (!(c0 & 1))
        f[i + 1][c + c0] += f[i][j];
      if (!(c1 & 1))
        f[i + 1][c] += f[i][j];
    }
    *s[0] = *s[1] = 0;
    for (int j = 0; j < n; ++j)
      s[a[j] >> i & 1][++*s[a[j] >> i & 1]] = a[j];
    for (int j = 1; j <= *s[0]; ++j)
      a[j - 1] = s[0][j];
    for (int j = 1; j <= *s[1]; ++j)
      a[*s[0] + j - 1] = s[1][j];
  }
  int sum = 0;
  for (int i = 1; i < n; ++i)
    sum ^= a[i] - a[0];
  printf("%lld\n", f[M - 1][0] - (sum == 0));
  return 0;
}