SRM 518 Nim FWT

发表于 2018-04-03 分类于算法小结

Nim游戏的规则不用说了。

已知堆数为n，每堆个数都为l以内的质数。

问有多少种方案使得后手必胜\(\bmod (10^9+7)\)。

\(n\le 10^9,l\le 50000\)

FWT板子题。

FWT是用来解决这样一类问题的：

给定\(A_i,B_i\)，求\(C_i=\sum_{a@b=i}A_aB_b\)。

其中\(@\)为任意一种位运算。

显然直接算需要\(O(n^2)\)，太慢了。

参考FFT，有没有一种变换\(ft(A)\)使得\(ft(A)_ift(B)_i=ft(C)_i\)并且\(ft\)及逆变换\(ift\)都可以在\(O(n\log n)\)的复杂度内算出来呢？

由于这个是位运算，可以只考虑某一位。

设\(A=(A_0,A_1)\) 当xor时，有一个优美的结论：

\(ft(A)=(ft(A_0)+ft(A_1),ft(A_0)-ft(A_1))\)

\(ift(A)=(\frac{ift(A_0)+ift(A_1)}{2},\frac{ift(A_0)-ift(A_1)}{2})\)

and则是：

\(ft(A)=(ft(A_0)+ft(A_1),ft(A_1))\)

\(ift(A)=(ift(A_0)-ift(A_1),ift(A_1))\)

or则是：

\(ft(A)=(ft(A_1),ft(A_0)+ft(A_1))\)

\(ift(A)=(ift(A_0),ift(A_1)-ift(A_0))\)

可以数学归纳证明。

NIM游戏要求如果xor和为0则后手必胜，也就是要求n堆xor和为0.

设\(a_i\)表示一堆能否组成i。

则答案为\(a_0^n\)

得到ft后直接快速幂即可。

时间复杂度\(O(n\log n)\)