【题解】CF1091H New Year and the Tricolore Recreation

CF1091H New Year and the Tricolore Recreation

现有一个 $n$ 行无限列的矩阵,每行从左往右有三个点 $b_i,w_i,r_i$,分别是蓝点、白点、红点。
$\texttt{Alice}$ 可以将蓝点/蓝点和白点向右移动 $k$ 格,$\texttt{Bob}$ 可以将红点/红点和白点向左移动 $k$ 格,不允许改变蓝白红点的相对位置,$k$ 是质数或两个质数的乘积,但是有一个值 $d$ 不能使用。无法操作者输。问先手必胜还是必败。
$n\le 10^5,-10^5\le b_i < w_i < r_i \le 10^5$。

$\texttt{Solution}$

两个人的操作方案不一样,不平等,因此考虑转化。

对于一行,蓝白红的相对位置不能改变,并且他们都在向着更中间移动。不难发现只有两个点之间的距离差有用,因此可以将一个状态表示成一个二元组 $(d_{bw},d_{wr})$,其中 $d_{bw}$ 是蓝白之间的距离,$d_{wr}$ 是白红之间的距离。

手玩一下,发现实际上 $\texttt{Alice}$ 移动蓝点和 $\texttt{Bob}$ 移动白点和红点是等价的,他们实际上都是把一个状态中的 $d_{bw}-k$,另两个操作同理。

然后就把一个看似操作不等价的问题变等价了。这样的话就每一行独立,可以每行分别求 $\texttt{SG}$ 然后异或起来。

所以现在把一行的问题转化为:

给定一个二元组 $(x,y)$,每次可以将 $x-k$ 或 $y-k$,其中 $k$ 是质数或两个质数的乘积。求 $\texttt{SG}$ 值。

又可以发现其中 $x,y$ 独立。那么现在就又转化为:

给定数字 $x$,每次将 $x-k$,其中 $k$ 是质数或两个质数的乘积。求 $\texttt{SG}$ 值。

首先质数和质数乘积不多,可以直接搞出来。观察一下发现 $\texttt{SG}$ 函数值也不会很大,设其最大值为 $\text{Max}$,那么如何快速求一个数 $x$ 的 $\texttt{SG}$ 值?

开 $\text{Max}$ 个大小 $2\times 10^5$ 的 $\texttt{bitset}$,第 $i$ 表示 $\texttt{SG}$ 值为 $i$ 的点能够转移到哪些点,求一个新点的 $\texttt{SG}$ 就直接扫一遍就行。

对于一个 $\texttt{SG}$ 为 $p$ 的点 $x$,在第 $p$ 个 $\texttt{bitset}$ 中需要进行更新,实际上就是把这个 $\texttt{bitset}$ 或上所有 $x+k$,$k$ 是质数或两个质数的乘积。

可以直接再开一个 $\texttt{bitset}$,记录所有质数和两个质数的乘积,把 $d$ 摘掉就行。然后每次更新就将这个 $\texttt{bitset}$ 左移 $x$ 位,或上去就行。

添加新评论