8月记录

237.Hitori的字符串(string)

AC 自动机上随机游走问题，但是叶子 \(\le 100\) 个，有环。

考虑设元然后高斯消元，但对每个点设显然不优，考虑一种链剖分，对链顶设元。

然后按照 bfs 序（trie 树上的）维护每个点期望的表示（用元表示）。

如果 \(tr_{x,i}\) 是返祖边，显然深度比 \(x\) 小，一定被表示了。

否则一定是链顶，可以被表示。

或者将度数 \(>1\) 的点设为关键点也能做，没细想。

238.Hitori玩游戏(nim)

考虑随机化，将一种方案的权值记为线性基中自由元个数。

每次取出一个集合，删掉选的数，选一个新的数，如果权值减小了，就替换当前方案，如果相等，就以一定概率替换。

将集合元素按照 \(1\) 的个数多少排序，shuffle 一下选择集合顺序即可。

239.Hitori摘樱桃(cherry)

根据小凯的疑惑，只有两个数 \(x,y\)，满足 \((x,y)=1\)，那么 \(xy-x-y\) 是最大的不能被表示的数。

证明可以考虑同余最短路，在模 \(x\) 的意义下 \(i\to (i+y)\bmod x\)，求出 \(f_i\) 表示 \(\bmod x =i\) 的最小能表示的数，将 \(f_i-x\) 取 \(\max\) 即可。

考虑这个图，就是一个环，可以手动模拟求出。

多个数也是一样的，求出所有数的 \(\gcd\)，记 \(x=\gcd \cdot a,y=\gcd\cdot b\)，那么 \((a,b)=1\)，在 \(\gcd \cdot a \gcd \cdot b=xy\) 之后，所有数（\(\gcd\) 的倍数）都能被表示。

对于 \(\le V\) 的数暴力背包，\(>V\) 的数每个 \(\gcd\) 的倍数都能被表示，我们相当于要求 \((px+100-p)^n \bmod x^m\)。

倍增 NTT 即可维护，每次缩减长度。

注意，可以计算所有数到离他最近的 \(\gcd\) 的距离，即后面这一部分，然后在前面背包的部分在加上每个数离他最近的 \(\gcd\) 到离他最近的可以取到的数的距离。