【题解】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$ 位，或上去就行。