SRM 518 Nim FWT

Nim游戏的规则不用说了。

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

问有多少种方案使得后手必胜

n109,l50000n\le 10^9,l\le 50000

FWT板子题。

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

给定Ai,BiA_i,B_i,求Ci=a@b=iAaBbC_i=\sum_{a@b=i}A_aB_b

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

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

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

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

A=(A0,A1)A=(A_0,A_1) 当xor时,有一个优美的结论:

ft(A)=(ft(A0)+ft(A1),ft(A0)ft(A1))ft(A)=(ft(A_0)+ft(A_1),ft(A_0)-ft(A_1))

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

and则是:

ft(A)=(ft(A0)+ft(A1),ft(A1))ft(A)=(ft(A_0)+ft(A_1),ft(A_1))

ift(A)=(ift(A0)ift(A1),ift(A1))ift(A)=(ift(A_0)-ift(A_1),ift(A_1))

or则是:

ft(A)=(ft(A1),ft(A0)+ft(A1))ft(A)=(ft(A_1),ft(A_0)+ft(A_1))

ift(A)=(ift(A0),ift(A1)ift(A0))ift(A)=(ift(A_0),ift(A_1)-ift(A_0))

可以数学归纳证明。

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

aia_i表示一堆能否组成i。

则答案为a0na_0^n

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

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

文章目录
|

博客使用Disqus作为评论系统