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

**题意** : 有 $n$ 堆石子，每堆有 $a_i$ 个石子和一个常数 $k_i$，两人轮流操作，每次可以从任意一堆（假设为第 $i$ 堆）石子中取出至少一个至多 $\lfloor\frac{a_i}{k_i}\rfloor$ 个。 不能操作者输。问是否先手必胜。 $n\leq 200,\ a_i,k_i\leq 10^9$ ，时限$\texttt{2s}$。 ------------ 这是经典的 $\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})$。 ```cpp #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; } ```