AtCoder Regular Contest 091 F - Strange Nim

题目大意

给你n个石子堆，然后Alice和Bob开始博弈。每个人每次可以从第i堆里面选出$[1,\lfloor \frac{ai}{ki}\rfloor ]$个石子。然后最后不能选的人就GG。

思考历程/题解

其实还是挺简单的，sg函数裸题。

先是想了个很暴力的dp方程，然后自以为可以线段树优化，结果发现很GG。
然后就想到了sg函数一般解法打表——分类讨论。
然后就一层一层地列，于是就发现了一些奇妙的规律。
当$1<=xi<ki$时：$0,0,0,\dots ,0$
当$ki<=xi<2ki$时：$1,0,1,0,\dots$
当$2ki<=xi<3ki$时：$2,\dots$
总之，能够观察到一个奇妙的结论：$sg[x]=\frac{x}{k}$当且仅当$x\%k=0$
然后我们就再通过sg函数mex的定义得到：$sg[x]=sg[x-\lfloor \frac{x}{k}\rfloor -1]$
于是就可以开心地递归啦~

WAIT A MINUTE!
当k很大的时候我们每次往前跳就会跳很短的距离。
这样时间复杂度还是会卡到$O(ai)$
于是考虑平衡规划一下。

• k<=100000，直接递归
• k>100000，考虑优化往前跳的过程。
  • 由于k比较大，所以一层的数也比较大。
  • 那就直接优化一个点在一层往前跳最远能跳到哪里。
  • 求出来之后如果不是最前面的点，则继续跳到下一层递归。
  • 否则输出$\frac{x}{k}$

然后就没了。
时间复杂度大致是$O(n\sqrt{ai})$

代码

#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdio>
using namespace std;

int n;
long long x[210],k[210],a[210];

long long findsg(int x,int k)
{
	if (x<k) return 0;
	if (x%k==0) return x/k;
	if (k>=100000)
	{
		long long op=x%k;
		long long oq=op%(x/k+1);
		x=k*(x/k)+oq;
		if (oq==0) return x/k;
		return findsg(x-x/k-1,k);
	}
	else
	return findsg(x-x/k-1,k);
}

int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
	{
		scanf("%lld%lld",&x[i],&k[i]);
		a[i]=findsg(x[i],k[i]);
	}
	long long ans=0;
	for (int i=1;i<=n;i++)
	{
		ans=ans^a[i];
	}
	if (ans!=0) printf("Takahashi\n");
	else printf("Aoki\n");
}