ARC091F Strange Nim 题解

作者: xht37 分类: 题解 发布时间: 2020-04-23 21:48

点击数:26

ARC091F Strange Nim

题意

  • 有 $n$ 堆石子,第 $i$ 堆有 $a_i$ 个石子和一个整数 $k_i$。
  • 两个人轮流,每次选择一堆,从中要取出至少一个石子
  • 设选择了第 $i$ 堆,当前还剩下 $x$ 个石子,则可以从中取出 $[1,\lfloor \frac{x}{k_i} \rfloor]$ 个石子。
  • 谁不能取了谁就输了,问最优策略下谁会获胜。
  • $n \le 200$,$a_i,k_i \le 10^9$。

题解

显然考虑每一堆的 SG 函数,若所有 SG 值异或起来为 $0$ 则后手赢,否则先手赢。

考虑如何计算 SG 函数,可以发现在 $k$ 意义下的 SG 函数 $sg(n)$ 的值为:
$$
sg(n) =\begin{cases}\frac nk & k \mid n \\sg(n – \lfloor \frac nk \rfloor – 1) & k \nmid n\end{cases}
$$
考虑根号分治计算 $sg(n)$,设 $w = \max_{i=1}^n a_i$。

若 $\lfloor \frac nk \rfloor \ge \sqrt w$,则直接转化为求 $g(n – \lfloor \frac nk \rfloor – 1)$,每次 $n$ 至少减少 $\sqrt w$,至多执行 $\mathcal O(\sqrt w)$ 次。

否则,一次性将 $n$ 减若干个 $\lfloor \frac nk \rfloor + 1$,直到 $\lfloor \frac nk \rfloor$ 改变或者 $k \mid n$,每次 $\lfloor \frac nk \rfloor$ 减少 $1$,至多执行 $\mathcal O(\sqrt w)$ 次。

总时间复杂度 $\mathcal O(n \sqrt w)$。

实现时不用分治,直接写就可以了。

代码

inline int SG(int n, int k) {
    int x = n / k, y = n % k;
    return y ? SG(n - (y + x) / (x + 1) * (x + 1), k) : x;
}

int main() {
    int n, w, k, ans = 0;
    rd(n);
    while (n--) rd(w, k), ans ^= SG(w, k);
    prints(ans ? "Takahashi" : "Aoki");
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注