ARC091F Strange Nim 题解

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