FWT快速变换

Fast Walsh Transformation,简称快速“华莱士”(沃尔什)变换,目的在于将一类与异或有关的多项式乘法优化为\( N \log N\)。

应用于优化形似\[c_{i} = \sum_{j} a_{j}\cdot b_{j \oplus i}\]的多项式乘法。

先看一道例题:

  • 题面

Alice 和Bob 在玩著名的Nim 游戏。在Nim 游戏中,有n 堆石子,每堆石子的个数分别为\(a_i \)。

双⽅轮流取石子,Alice 先。每一轮,玩家可以选择任意一非空的石子堆,并从这一堆石子中取至少一个至多全部个石子。取走所有石子中的最后一颗石子的人获胜。

由于Alice 和Bob 非常喜欢素数,他们决定让\(a_i \)是不超过L 的任意一个素数。Bob 由于技术不佳,所以他经常输。现在,他想知道,有多少个初始局面,使得无论Alice 如何取,自己都有策略赢。

  • 输入

n L

  • 输出

ans mod 1000000007

  • 样例输入

4 13

  • 样例输出

120

  • 数据范围

n \(\leq \) 10^9   L \(\leq \) 50000


博弈论?

这是一道显然的博弈论

首先我们要用到最基础的博弈论知识:

对于一个nim游戏,当\(a_1 \oplus  a_2 \oplus … \oplus a_n = 0 \)时为P-situation,此时先手必败,否则为N-situation,此时先手必胜

详见nim游戏详解,Alice与Bob的第一个故事


动态规划

这时我们得到了第一种做法:dp,由于L不大,考虑用数值设计状态

f[i][j]表示已经放了i堆石子,每堆石子个数异或起来得到的值是j的方案数,这里注意j的上界为\(2^{\log_2L + 1} \)

\[ f[i][j]=\sum_{isprime(k \oplus j)}^k f[i-1][k] \]


矩阵快速幂

我们发现这个dp方程可以用矩阵快速幂进行优化

设一个转移矩阵,横行与纵行分别表示\(0 – 2^{ \log_2 L + 1} \)的所有整数,第i行第j列的值为\(isprime(k \oplus j) \)

这样我们把N优化为了\( \log N \)


FWT

我们现在有了一个\( O \left ( L ^ 2 \log N \right ) \)的做法

考虑对其进行优化,我们令a=dp[i], b=dp[j], c=dp[i+j],考虑a, b, c的关系

又回到了本文开始提到的式子\[c_{i} = \sum_{j} a_{j}\cdot b_{j \oplus i}\]

这个等式直接求值复杂度是\( O \left ( N^2 \right ) \),我们需要一个优化这个等式求值的方法,考虑分治

我们把\( c_i \)中的i写做二进制形式,如101011101,把这个数的最高位1单独拿出来,后面一部分01011101写作x,则

\[ c_{(0x)_2} = \sum_{(0y)_2} a_{(0y)_2}b_{(0 (y \oplus x))_2} + \sum_{(1y)_2} a_{(1y)_2}b_{(1 (y \oplus x))_2} \]

\[ c_{(1x)_2} = \sum_{(0y)_2} a_{(0y)_2}b_{(1 (y \oplus x))_2} + \sum_{(1y)_2} a_{(1y)_2}b_{(0 (y \oplus x))_2} \]

这样我们就把数据规模减小了一倍,考虑分治

很显然这两个式子分开看没有方法分治,那我们把它们加起来

\[ c_{(0x)_2} + c_{(1x)_2} = \sum_{(y)_2} ( a_{(0y)_2} + a_{(1y)_2} ) ( b_{(0(y \oplus x))_2} + b_{(1(y \oplus x))_2} ) \]

同理,我们把它们相减

\[ c_{(0x)_2} – c_{(1x)_2} = \sum_{(y)_2} ( a_{(0y)_2} – a_{(1y)_2} ) ( b_{(0(y \oplus x))_2} – b_{(1(y \oplus x))_2} ) \]

我们发现,我们通过变换得到的式子与原来的式子\( c_{i} = \sum_{j} a_{j}\cdot b_{j \oplus i} \)是相似的

我们可以每次把初始的式子转换为新的两个式子,每次重复相同的过程,到达底层直接返回值,通过返回得到的\( c_{(0x)_2} + c_{(1x)_2} \)与\( c_{(0x)_2} – c_{(1x)_2} \)得到\( c_{(0x)_2} \)与\( c_{(1x)_2} \)再返回。

于是我们就可以进行分治,每次范围缩小一倍,一共\( \log N \)层,这样我们就得到了一个\( N \log N \)的方法


然而这并没有什么卵用,我们这种做法与原来的矩阵乘法其实没有什么效率上的区别(可用于装逼),于是我们考虑根据我们这种算法可递归的神奇性质来进行优化。

我们原来的做法是直接对a,b进行FWT(a,b),也就是对a,b进行分治


此坑待填

点赞
  1. fstqwq说道:

    "Alex与Bob的第一个故事"
    ->
    "Alice与Bob的第一个故事"

    1. HenryPigLi说道:

      这是一个失误 :neutral:

发表评论

电子邮件地址不会被公开。 必填项已用*标注