A. 取石子游戏

容易发现这个问题的 $sg$ 值就是每堆的石子个数的异或和。

问题是后手能赢，也就是求删除 $d$ 的倍数个石子，使得剩余石子的异或和恰好为 $0$ 的方案数。

然后发现直接 $dp$ 复杂度就是 $O(n*d*\max(a_i))$ 的。

发现题面中给出了一个很特殊的限制，所以考虑如何做到每次 $O(d*a_i)$ 的转移。

容易发现给 $a_i$ 排个序就好了。

坑点是不能全删完，所以当 $d$ 是 $n$ 的因数的时候需要给答案减一个 $1$。

B. 路径计数

容易发现不同的询问个数并不多，所以这题肯定要预处理答案。

这样直接做一个 $dp$，复杂度就是 $O(n^4d)$的。

然后发现这个 $n^4$ 是枚举点对+枚举边，肯定后者省不掉，所以想一下怎么把枚举点对转化为枚举一个点。

比如枚举起点，那考虑弄一个容斥出答案。

现在不妨让路径上都不经过起点，那么只要钦定路径上出现若干个终点，即可容斥出路径上恰好出现 $0$ 次终点。

然后考虑每个钦定序列的方案数，发现这个玩意有两种形式。

设 $f(i,j,x,k)$ 表示由 $i$ 走 $k$ 步到达 $j$，路径上不能经过 $x$ 的方案数。

那么一个是 $f(s,t,s,k)$ ，一个是 $f(t,t,s,k)$ 。

前者直接做一下 $O(n^3d)$ 的 $dp$ 就完事了，后者再套一个类似的容斥即可转化为没有任何限制，也就是个直接 $dp$。

但是容斥的方法是枚举序列，这肯定不现实，容易发现只关心终点的最后一次出现，所以写成类似背包 $dp$ 的形式就好了。

C. 方格操作

考虑设 $f_x$ 表示第 $x$ 行 $1$ 出现次数的奇偶性， $g_x$ 同理表示列。

然后发现一***作之后，有 $col_{i,j}=f_i \ xor \ g_j$。

然后有一个想不到但挺显然的结论，就是说行、列的交换是不影响答案的。

那么发现把 $f,g$ 的两种取值分别移动到角落，第一***作之后，形成的就是四个矩形。

既然第一轮是矩形，以后的每一轮这个矩形始终存在，并且每个矩形中每个点的颜色是相同的。

所以直接模拟，因为只有四个矩形，当超过 $16$ 轮模拟仍然没有结束，那肯定就是操作无限次了。

所以问题只剩下如何求初始的 $f,g$ ，发现这个搞个扫描线就好了。