[数学记录]AT3939 [ARC091D] Strange Nim

· · 个人记录

题意 : 有 n 堆石子，每堆有 a_i 个石子和一个常数 k_i，两人轮流操作，每次可以从任意一堆（假设为第 i 堆）石子中取出至少一个至多 \lfloor\frac{a_i}{k_i}\rfloor 个。

不能操作者输。问是否先手必胜。

------------ 这是经典的 $\rm SG$ 和问题，求出每一堆的 $\rm SG$ 函数然后异或即可。 对于一堆石子 $(a,k)$ ，其后继状态为 $(a-\lfloor a/k\rfloor\sim a-1,k)$。 我们将 $\lfloor a/k\rfloor$ 相同的一组状态一起研究。 对于状态 $(ck\sim (c+1)k-1)$ ，一步最多拿走的石子数目均为 $c$。 显然状态 $(0\sim k-1,k)$ 都是无法操作的，故 $\rm SG$ 值为 $0$。 打表不难看出 $SG(ck,k)=c$。 而 $c$ 达到了后继状态总数，这说明 $SG(ck-1,k)\sim SG(ck-c,k)$ 为 $0\sim c-1$ 的排列。 考虑 $SG(ck+1,k)$ ，其后继状态为 $SG(ck,k)\sim SG(ck-c+1,k)$ ，其中 $SG(ck,k)$ 达到了后继状态数，无贡献。 其他部分 $SG(ck-1,k)\sim SG(ck-c+1,k)$ 相当于 $0\sim c-1$ 的排列去掉了 $SG(ck-c)$ ，故有 $SG(ck+1,k)=SG(ck-c)$。 进一步考虑 $SG(ck+2,k)$ ，能发现是 $0\sim c-1$ 的排列去掉了 $SG(ck-c+1)$ ，故有 $SG(ck+2,k)=SG(ck-c+1)

依次类推，则有 SG(ck+t)=SG(ck-c+t-1)。

能写出如下递推公式。

SG(a,k)= \begin{cases} 0&(0\leq a<k)\\ a/k&(k|a)\\ SG(a-\lfloor a/k\rfloor-1,k) &(\rm otherwise) \end{cases}

进一步地， SG((c+1)k) ，后继状态为 SG(ck+c-1,k)\sim SG(ck,k) ，正是 0\sim c 的排列，于是 SG((c+1)k)=c+1 ，能归纳证明结论。

若根据上述公式直接计算 SG 函数，复杂度较劣。

考虑在转移中将 \lfloor a/k\rfloor 相等的步骤一起做。

对 (a,k) ，记 x=\lfloor a/k\rfloor ，找出最大的 y 使得 y 次转移都是第三种情况。

即 a-(y-1)(x+1)+1\geq xk ，则 y=\left\lfloor\frac{a\bmod k-1}{x+1}\right\rfloor+1。

这 y 次转移都是第三种情况，所以可以直接令 SG(a,k)=SG(a-(x+1)y,k)。

考虑复杂度，当 k\leq \sqrt{a} ， \lfloor a/k\rfloor 本身就 \geq \sqrt{a} 。

当 k> \sqrt{a} ， \lfloor a/k\rfloor 只有 O(\sqrt{a}) 种不同取值。

综上，总杂度为 O(n\sqrt{a})。

#include<algorithm>
#include<cstdio>
using namespace std;
int f(int n,int k) 
{
  if (n<k)return 0;
  if (n%k==0)return n/k;
  int x=n/k,y=(n%k-1)/(x+1)+1;
  return f(n-y*(x+1),k);
}
int n;
int main()
{
  scanf("%d",&n);
  int ans=0;
  for (int i=1,a,k;i<=n;i++){
    scanf("%d%d",&a,&k);
    ans^=f(a,k);
  }puts(ans==0 ? "Aoki" : "Takahashi");
  return 0;
}