SRM 518 Nim FWT
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)$