CF1033G Chip Game 题解

· · 题解

Link.

Luogu
Codeforces

Description.

Alice Bob 分别可以从任意一堆中取出 $A$、$B$ 个石子，不能操作的人输。 问对于不同的 $A,B$，以下四种状态的方案数分别是多少。 1. Alice 赢 2. Bob 赢 3. 先手赢 4. 后手赢 $n\le 100,m\le 10^5

Solution.

首先，发现 Alice 赢和 Bob 赢本质相同，方案数相同。
所以我们只需要算出先手赢、后手赢的方案数容斥就行了。

同时，显然的性质就是状态 \{v_i\} 和状态 \{v_i+k_i(a+b)\} 等价。
证明显然，赢的人肯定可以按照原来状态，如果后手选了就跟他把 k_i 减一。

那我们可以考虑枚举 a+b，剩下了所有的 v_i\le (a+b)。
考虑先手赢，可能会有这几种情况

先手能苟的情况也就只有这两种。
考虑不能苟，那也就是说 \sum[v_i\ge b] 是偶数。
所以先手必败的情况是没有情况 1 和 2 且是偶数。
同理，后手赢的情况有以下几种

  1. \exists i\in[1,n],b\le v_i< a
  2. \sum[2b\le v_i]\ge 2

考虑 \forall i\in[1,n],a\le v_i<b 不成立，则肯定有 a,b 在同一个 (v_i,v_{i+1}] 值域区间内。
所以我们可以枚举这个值域区间，复杂度 O(n)，可以 O(1) 算出 \sum[v_i\ge b]。
考虑 2a\le v_i 也不成立，所以肯定有 a>\frac {v_i}2，直接找到最大的 v_i 就行了。
后手的话考虑次大就行了。