【AT3939】[ARC091D] Strange Nim(博弈论)

2021/5/9 18:56:05

本文主要是介绍【AT3939】[ARC091D] Strange Nim(博弈论),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

点此看题面

  • 有\(n\)堆石子,每堆石子初始有\(a_i\)个,且附带一个参数\(k_i\)。
  • 每次可以从一堆石子(假设是第\(i\)堆,当前剩\(x_i\)个石子)中取出\(1\sim\lfloor\frac{x_i}{k_i}\rfloor\)个石子,判断谁必胜。
  • \(n\le200,a_i,k_i\le10^9\)

\(SG\)函数

根据\(Nim\)游戏的基本知识我们知道可以分别求出每堆石子的\(SG\)函数,然后异或在一起就是全局的\(SG\)函数了。

一个显然的转移式:

\[SG(x)=\texttt{mex}_{i=1}^{\lfloor\frac xk\rfloor}SG(x-i) \]

看起来很诡异,但我们仔细想想便会找到一个性质,就是\(x\)的前\(\lfloor\frac xk\rfloor+1\)位应该是一个\(0\sim \lfloor\frac xk\rfloor\)的排列!

但如果\(x\)是\(k\)的倍数时会存在例外,此时它的前\(\lfloor\frac xk\rfloor\)位是一个\(0\sim \lfloor\frac xk\rfloor-1\)的排列,因此\(SG(x)=\lfloor\frac xk\rfloor\)。

证明只需归纳即可,应该还是比较容易的。

那么我们可以列出一个简单的递推式:

\[SG(x)=\begin{cases}0&x<k,\\\lfloor\frac xk\rfloor&k|x,\\SG(x-\lfloor\frac xk\rfloor-1)&x>k\&\&k\not|x\end{cases} \]

主要是考虑第三种转移,直接搞复杂度是\(O(k)\)的,如果\(k\)很大可能会挂。

但我们发现对于\(\lfloor\frac xk\rfloor\)相等的连续一段其实可以放一起转移,那么就只会转移\(O(\lfloor\frac ak\rfloor)\)次。

二者一结合,复杂度就是\(O(\sqrt a)\)的,正确了。

代码:\(O(n\sqrt a)\)

#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
using namespace std;
int n;I int SG(CI x,CI k)//求SG函数
{
	if(x<k) return 0;if(!(x%k)) return x/k;//x<k和x是k倍数的两种情况
	RI y=x/k*k,d=x/k+1,t=(x-y)/d;return SG(x-max(t,1)*d,k);//x/k相同的一段一起转移
}
int main()
{
	RI i,x,k,t=0;for(scanf("%d",&n),i=1;i<=n;++i) scanf("%d%d",&x,&k),t^=SG(x,k);//把每堆石子的SG函数异或起来
	return puts(t?"Takahashi":"Aoki"),0;
}


这篇关于【AT3939】[ARC091D] Strange Nim(博弈论)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程