题解 | #E#

E 题解

先对 SG 进行打表发现 $SG[i]=[i\mathrm{/}3]SG[i]=[i/3]$。

考虑第一次操作的三角形三条边跨越 $a,b,ca,b,c$ 条边，则剩下为 $SG[a-1]xorSG[b-1]xorSG[c-1]SG[a-1]\; xor\; SG[b-1]\; xor\; SG[c-1]$ 要等于 $00$ 才能赢。

先枚举这三个数 $\mathrm{m}\mathrm{o}\mathrm{d}3\backslash bmod\; 3$ 得到的余数，这样剩下部分都是 $33$ 的倍数，直接除以 $33$ 就是 SG 了。

问题转换成了对于一定值 $nn$ 求有多少 $a+b+(axorb)=na+b+(a\; xor\; b)=n$。

从低到高考虑 $nn$ 的每一位 $a,ba,b$ 怎么选。容易发现如果都选 $00$ 就不会进位，否则就有进位。

同时 $nn$ 最低位必须是 $00$，所以只会进其中一个分支，这样就能递归算了。

最后形状相同的可以旋转，答案要乘上 $nn$。

复杂度 $3^3\times \log n3^3\backslash times\; \backslash log\; n$。