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)$

# FWT
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×