跳转至

# 快速沃尔什变换

## 简介

沃尔什转换（Walsh Transform）1是在频谱分析上作为离散傅立叶变换的替代方案的一种方法，在信号处理中应用很广泛．FFT 是 double 类型的，但是 Walsh 把信号在不同震荡频率方波下拆解，因此所有的系数都是绝对值大小相同的整数，这使得不需要作浮点数的乘法运算，提高了运算速度．

所以，FWT 和 FFT 的核心思想应该是相同的，都是对数组的变换．我们记对数组 𝐴 A 进行快速沃尔什变换后得到的结果为 𝐹 𝑊 𝑇[𝐴]F W T[A]．

那么 FWT 核心思想就是：

我们需要一个新序列 𝐶 C，由序列 𝐴 A 和序列 𝐵 B 经过某运算规则得到，即 𝐶 =𝐴 ⋅𝐵 C=A⋅B；

我们先正向得到序列 𝐹 𝑊 𝑇[𝐴],𝐹 𝑊 𝑇[𝐵]F W T[A],F W T[B]，再根据 𝐹 𝑊 𝑇[𝐶] =𝐹 𝑊 𝑇[𝐴] ⋅𝐹 𝑊 𝑇[𝐵]F W T[C]=F W T[A]⋅F W T[B] 在 𝑂(𝑛)O(n) 的时间复杂度内求出 𝐹 𝑊 𝑇[𝐶]F W T[C]，其中 ⋅⋅ 是序列对应位置相乘；

然后逆向运算得到原序列 𝐶 C．时间复杂度为 𝑂(𝑛 l o g⁡𝑛)O(n log⁡n)．

在算法竞赛中，FWT 是用于解决对下标进行位运算卷积问题的方法．

公式：𝐶 𝑖 =∑𝑖=𝑗⊕𝑘 𝐴 𝑗 𝐵 𝑘 C i=∑i=j⊕k A j B k

（其中 ⊕⊕ 是二元位运算中的某一种）

下面我们举 ∪∪（按位或）、∩∩（按位与）和 ⊕⊕（按位异或）为例．

## FWT 的运算

### 或运算

如果有 𝑘 =𝑖 ∪𝑗 k=i∪j，那么 𝑖 i 的二进制位为 1 1 的位置和 𝑗 j 的二进制位为 1 1 的位置肯定是 𝑘 k 的二进制位为 1 1 的位置的子集．

现在要得到 𝐹 𝑊 𝑇[𝐶] =𝐹 𝑊 𝑇[𝐴] ⋅𝐹 𝑊 𝑇[𝐵]F W T[C]=F W T[A]⋅F W T[B]，我们就要构造这个 FWT 的规则．

我们按照定义，显然可以构造 𝐹 𝑊 𝑇[𝐴]𝑖 =𝐴′𝑖 =∑𝑖=𝑖∪𝑗 𝐴 𝑗 F W T[A]i=A i′=∑i=i∪j A j，来表示 𝑗 j 满足二进制中 1 1 为 𝑖 i 的子集．

那么有：

𝐹 𝑊 𝑇[𝐴]𝑖⋅𝐹 𝑊 𝑇[𝐵]𝑖=(∑𝑖∪𝑗=𝑖 𝐴 𝑗)(∑𝑖∪𝑘=𝑖 𝐵 𝑘)=∑𝑖∪𝑗=𝑖∑𝑖∪𝑘=𝑖 𝐴 𝑗 𝐵 𝑘=∑𝑖∪(𝑗∪𝑘)=𝑖 𝐴 𝑗 𝐵 𝑘=𝐹 𝑊 𝑇[𝐶]𝑖 F W T[A]i⋅F W T[B]i=(∑i∪j=i A j)(∑i∪k=i B k)=∑i∪j=i∑i∪k=i A j B k=∑i∪(j∪k)=i A j B k=F W T[C]i

那么我们接下来看 𝐹 𝑊 𝑇[𝐴]F W T[A] 怎么求．

首先肯定不能枚举了，复杂度为 𝑂(𝑛 2)O(n 2)．既然不能整体枚举，我们就考虑分治．

我们把整个区间二分，其实二分区间之后，下标写成二进制形式是有规律可循的．

我们令 𝐴 0 A 0 表示 𝐴 A 的前一半，𝐴 1 A 1 表示区间的后一半，那么 𝐴 0 A 0 就是 A 下标最大值的最高位为 0 0，他的子集就是他本身的子集（因为最高位为 0 0 了），但是 𝐴 1 A 1 的最高位是 1 1，他满足条件的子集不仅仅是他本身，还包最高位为 0 0 的子集，即

𝐹 𝑊 𝑇[𝐴]=𝑚 𝑒 𝑟 𝑔 𝑒(𝐹 𝑊 𝑇[𝐴 0],𝐹 𝑊 𝑇[𝐴 0]+𝐹 𝑊 𝑇[𝐴 1])F W T[A]=m e r g e(F W T[A 0],F W T[A 0]+F W T[A 1])

其中 merge 表示像字符串拼接一样把两个数组拼起来，++ 就是普通加法，表示对应二进制位相加．

这样我们就通过二分能在 𝑂(l o g⁡𝑛)O(log⁡n) 的时间复杂度内完成拼接，每次拼接的时候要完成一次运算，也就是说在 𝑂(𝑛 l o g⁡𝑛)O(n log⁡n) 的时间复杂度得到了 𝐹 𝑊 𝑇[𝐴]F W T[A]．

接下来就是反演了，其实反演是很简单的，既然知道了 𝐴 0 A 0 的本身的子集是他自己（𝐴 0 =𝐹 𝑊 𝑇[𝐴 0]A 0=F W T[A 0]），𝐴 1 A 1 的子集是 𝐹 𝑊 𝑇[𝐴 0] +𝐹 𝑊 𝑇[𝐴 1]F W T[A 0]+F W T[A 1]，那就很简单的得出反演的递推式了：

𝑈 𝐹 𝑊 𝑇[𝐴′]=𝑚 𝑒 𝑟 𝑔 𝑒(𝑈 𝐹 𝑊 𝑇[𝐴′0],𝑈 𝐹 𝑊 𝑇[𝐴′1]−𝑈 𝐹 𝑊 𝑇[𝐴′0])U F W T[A′]=m e r g e(U F W T[A 0′],U F W T[A 1′]−U F W T[A 0′])

下面我们给出代码实现．容易发现顺变换和逆变换可以合并为一个函数，顺变换时 t y p e =1 type=1，逆变换时 t y p e = −1 type=−1．

实现

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    void Or(ll *a, ll type) {  // 迭代实现，常数更小
      for (ll x = 2; x <= n; x <<= 1) {
        ll k = x >> 1;
        for (ll i = 0; i < n; i += x) {
          for (ll j = 0; j < k; j++) {
            (a[i + j + k] += a[i + j] * type) %= P;
          }
        }
      }
    }

### 与运算

与运算类比或运算可以得到类似结论

𝐹 𝑊 𝑇[𝐴]=𝑚 𝑒 𝑟 𝑔 𝑒(𝐹 𝑊 𝑇[𝐴 0]+𝐹 𝑊 𝑇[𝐴 1],𝐹 𝑊 𝑇[𝐴 1])F W T[A]=m e r g e(F W T[A 0]+F W T[A 1],F W T[A 1])𝑈 𝐹 𝑊 𝑇[𝐴′]=𝑚 𝑒 𝑟 𝑔 𝑒(𝑈 𝐹 𝑊 𝑇[𝐴′0]−𝑈 𝐹 𝑊 𝑇[𝐴′1],𝑈 𝐹 𝑊 𝑇[𝐴′1])U F W T[A′]=m e r g e(U F W T[A 0′]−U F W T[A 1′],U F W T[A 1′])

下面我们给出代码实现．顺变换时 t y p e =1 type=1，逆变换时 t y p e = −1 type=−1．

实现

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    void And(ll *a, ll type) {
      for (ll x = 2; x <= n; x <<= 1) {
        ll k = x >> 1;
        for (ll i = 0; i < n; i += x) {
          for (ll j = 0; j < k; j++) {
            (a[i + j] += a[i + j + k] * type) %= P;
          }
        }
      }
    }

### 异或运算

异或的卷积是基于如下原理：

若我们令 𝑥 ∘𝑦 x∘y 表示 𝑥 ∩𝑦 x∩y 中 1 1 数量的奇偶性，即 𝑥 ∘𝑦 =p o p c n t(𝑥 ∩𝑦)m o d 2 x∘y=popcnt(x∩y)mod 2，那么容易有 (𝑥 ∘𝑦) ⊕(𝑥 ∘𝑧) =𝑥 ∘(𝑦 ⊕𝑧)(x∘y)⊕(x∘z)=x∘(y⊕z)．

对于 𝐹 𝑊 𝑇[𝐴]F W T[A] 的运算其实也很好得到．

设 𝐹 𝑊 𝑇[𝐴]𝑖 =∑𝑖∘𝑗=0 𝐴 𝑗 −∑𝑖∘𝑗=1 𝐴 𝑗 F W T[A]i=∑i∘j=0 A j−∑i∘j=1 A j．我们来证一下 𝐹 𝑊 𝑇[𝐶] =𝐹 𝑊 𝑇[𝐴] ⋅𝐹 𝑊 𝑇[𝐵]F W T[C]=F W T[A]⋅F W T[B] 的正确性：

𝐹 𝑊 𝑇[𝐴]𝑖 𝐹 𝑊 𝑇[𝐵]𝑖=(∑𝑖∘𝑗=0 𝐴 𝑗−∑𝑖∘𝑗=1 𝐴 𝑗)(∑𝑖∘𝑘=0 𝐵 𝑘−∑𝑖∘𝑘=1 𝐵 𝑘)=(∑𝑖∘𝑗=0 𝐴 𝑗∑𝑖∘𝑘=0 𝐵 𝑘+∑𝑖∘𝑗=1 𝐴 𝑗∑𝑖∘𝑘=1 𝐵 𝑘)−(∑𝑖∘𝑗=0 𝐴 𝑗∑𝑖∘𝑘=1 𝐵 𝑘+∑𝑖∘𝑗=1 𝐴 𝑗∑𝑖∘𝑘=0 𝐵 𝑘)=∑(𝑗⊕𝑘)∘𝑖=0 𝐴 𝑗 𝐵 𝑘−∑(𝑗⊕𝑘)∘𝑖=1 𝐴 𝑗 𝐵 𝑘=𝐹 𝑊 𝑇[𝐶]𝑖 F W T[A]i F W T[B]i=(∑i∘j=0 A j−∑i∘j=1 A j)(∑i∘k=0 B k−∑i∘k=1 B k)=(∑i∘j=0 A j∑i∘k=0 B k+∑i∘j=1 A j∑i∘k=1 B k)−(∑i∘j=0 A j∑i∘k=1 B k+∑i∘j=1 A j∑i∘k=0 B k)=∑(j⊕k)∘i=0 A j B k−∑(j⊕k)∘i=1 A j B k=F W T[C]i

来看看怎么快速计算 𝐴,𝐵 A,B 的值，依旧是分治：

对于 𝑖 i 在当前位为 0 0 的子数列 𝐹 𝑊 𝑇[𝐴 0]F W T[A 0]，进行 ∘∘ 运算时发现它和 0 0 计算或和 1 1 计算结果都不会变（因为 0 ∩0 =0,0 ∩1 =0 0∩0=0,0∩1=0），所以 𝐹 𝑊 𝑇[𝐴] =∑𝑖∘𝑗=0 𝐴 𝑗 −∑𝑖∘𝑗=1 𝐴 𝑗 F W T[A]=∑i∘j=0 A j−∑i∘j=1 A j 中的 ∑𝑖∘𝑗=1 𝐴 𝑗 =0∑i∘j=1 A j=0．

对于 𝑖 i 在当前位为 1 1 的子数列 𝐴 1 A 1，进行 ∘∘ 运算时发现它和 0 0 计算结果是 0 0，和 1 1 计算结果是 1 1（因为 1 ∩0 =0,1 ∩1 =1 1∩0=0,1∩1=1）．

综上，有：

𝐹 𝑊 𝑇[𝐴]=𝑚 𝑒 𝑟 𝑔 𝑒((𝐹 𝑊 𝑇[𝐴 0]+𝐹 𝑊 𝑇[𝐴 1])−0,𝐹 𝑊 𝑇[𝐴 0]−𝐹 𝑊 𝑇[𝐴 1])F W T[A]=m e r g e((F W T[A 0]+F W T[A 1])−0,F W T[A 0]−F W T[A 1])

也就是：

𝐹 𝑊 𝑇[𝐴]=𝑚 𝑒 𝑟 𝑔 𝑒(𝐹 𝑊 𝑇[𝐴 0]+𝐹 𝑊 𝑇[𝐴 1],𝐹 𝑊 𝑇[𝐴 0]−𝐹 𝑊 𝑇[𝐴 1])F W T[A]=m e r g e(F W T[A 0]+F W T[A 1],F W T[A 0]−F W T[A 1])

逆变换易得：

𝑈 𝐹 𝑊 𝑇[𝐴′]=𝑚 𝑒 𝑟 𝑔 𝑒(𝑈 𝐹 𝑊 𝑇[𝐴′0]+𝑈 𝐹 𝑊 𝑇[𝐴′1]2,𝑈 𝐹 𝑊 𝑇[𝐴′0]−𝑈 𝐹 𝑊 𝑇[𝐴′1]2)U F W T[A′]=m e r g e(U F W T[A 0′]+U F W T[A 1′]2,U F W T[A 0′]−U F W T[A 1′]2)

给出代码，顺变换时 t y p e =1 type=1，逆变换时 t y p e =1 2 type=1 2．

实现

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    void Xor(ll *a, ll type) {
      for (ll x = 2; x <= n; x <<= 1) {
        ll k = x >> 1;
        for (ll i = 0; i < n; i += x) {
          for (ll j = 0; j < k; j++) {
            (a[i + j] += a[i + j + k]) %= P;
            (a[i + j + k] = a[i + j] - a[i + j + k] * 2) %= P;
            (a[i + j] *= type) %= P;
            (a[i + j + k] *= type) %= P;
          }
        }
      }
    }

### 同或运算

类比异或运算给出公式：

𝐹 𝑊 𝑇[𝐴]𝑖 =∑𝐶 1 𝐴 𝑗 −∑𝐶 2 𝐴 𝑗 F W T[A]i=∑C 1 A j−∑C 2 A j（𝐶 1 C 1 表示 p o p c n t(𝑥 ∪𝑦)m o d 2 popcnt(x∪y)mod 2 为 0 0，𝐶 2 C 2 表示 p o p c n t(𝑥 ∪𝑦)m o d 2 popcnt(x∪y)mod 2 为 1 1）

𝐹 𝑊 𝑇[𝐴]=𝑚 𝑒 𝑟 𝑔 𝑒(𝐹 𝑊 𝑇[𝐴 1]−𝐹 𝑊 𝑇[𝐴 0],𝐹 𝑊 𝑇[𝐴 1]+𝐹 𝑊 𝑇[𝐴 0])F W T[A]=m e r g e(F W T[A 1]−F W T[A 0],F W T[A 1]+F W T[A 0])𝑈 𝐹 𝑊 𝑇[𝐴′]=𝑚 𝑒 𝑟 𝑔 𝑒(𝑈 𝐹 𝑊 𝑇[𝐴′1]−𝑈 𝐹 𝑊 𝑇[𝐴′0]2,𝑈 𝐹 𝑊 𝑇[𝐴′1]+𝑈 𝐹 𝑊 𝑇[𝐴′0]2)U F W T[A′]=m e r g e(U F W T[A 1′]−U F W T[A 0′]2,U F W T[A 1′]+U F W T[A 0′]2)

## 另一个角度的 FWT

我们设 𝑐(𝑖,𝑗)c(i,j) 是 𝐴 𝑗 A j 对 𝐹 𝑊 𝑇[𝐴]𝑖 F W T[A]i 的贡献系数．我们可以重新描述 FWT 变换的过程：

𝐹 𝑊 𝑇[𝐴]𝑖=𝑛−1∑𝑗=0 𝑐(𝑖,𝑗)𝐴 𝑗 F W T[A]i=∑j=0 n−1 c(i,j)A j

因为有：

𝐹 𝑊 𝑇[𝐴]𝑖⋅𝐹 𝑊 𝑇[𝐵]𝑖=𝐹 𝑊 𝑇[𝐶]𝑖 F W T[A]i⋅F W T[B]i=F W T[C]i

所以我们可以通过简单的证明得到：𝑐(𝑖,𝑗)𝑐(𝑖,𝑘) =𝑐(𝑖,𝑗 ⊙𝑘)c(i,j)c(i,k)=c(i,j⊙k)．其中 ⊙⊙ 是任意一种位运算．

同时，𝑐 c 函数还有一个重要的性质，它可以按位处理．

举个例子，我们变换的时候：

𝐹 𝑊 𝑇[𝐴]𝑖=𝑛−1∑𝑗=0 𝑐(𝑖,𝑗)𝐴 𝑗 F W T[A]i=∑j=0 n−1 c(i,j)A j

这么做是比较劣的，我们将其拆分：

𝐹 𝑊 𝑇[𝐴]𝑖=𝑛/2−1∑𝑗=0 𝑐(𝑖,𝑗)𝐴 𝑗+𝑛−1∑𝑗=𝑛/2 𝑐(𝑖,𝑗)𝐴 𝑗 F W T[A]i=∑j=0 n/2−1 c(i,j)A j+∑j=n/2 n−1 c(i,j)A j

考虑前面的式子和后面的式子 𝑖,𝑗 i,j 的区别，发现只有最高位不同．

所以我们将 𝑖,𝑗 i,j 去除最高位的值为 𝑖′,𝑗′i′,j′，并记 𝑖 0 i 0 为 𝑖 i 的最高位．有：

𝐹 𝑊 𝑇[𝐴]𝑖=𝑐(𝑖 0,0)𝑛/2−1∑𝑗=0 𝑐(𝑖′,𝑗′)𝐴 𝑗+𝑐(𝑖 0,1)𝑛−1∑𝑗=𝑛/2 𝑐(𝑖′,𝑗′)𝐴 𝑗 F W T[A]i=c(i 0,0)∑j=0 n/2−1 c(i′,j′)A j+c(i 0,1)∑j=n/2 n−1 c(i′,j′)A j

如果 𝑖 0 =0 i 0=0，则有：

𝐹 𝑊 𝑇[𝐴]𝑖=𝑐(0,0)𝑛/2−1∑𝑗=0 𝑐(𝑖′,𝑗′)𝐴 𝑗+𝑐(0,1)𝑛−1∑𝑗=𝑛/2 𝑐(𝑖′,𝑗′)𝐴 𝑗 F W T[A]i=c(0,0)∑j=0 n/2−1 c(i′,j′)A j+c(0,1)∑j=n/2 n−1 c(i′,j′)A j

𝑖 0 =1 i 0=1 则有：

𝐹 𝑊 𝑇[𝐴]𝑖=𝑐(1,0)𝑛/2−1∑𝑗=0 𝑐(𝑖′,𝑗′)𝐴 𝑗+𝑐(1,1)𝑛−1∑𝑗=𝑛/2 𝑐(𝑖′,𝑗′)𝐴 𝑗 F W T[A]i=c(1,0)∑j=0 n/2−1 c(i′,j′)A j+c(1,1)∑j=n/2 n−1 c(i′,j′)A j

也就是说，我们只需要：

[𝑐(0,0)𝑐(0,1)𝑐(1,0)𝑐(1,1)][c(0,0)c(0,1)c(1,0)c(1,1)]

四个数就可以完成变换了．我们称这个矩阵为位矩阵．

如果我们要进行逆变换，则需要上面的位矩阵的逆矩阵．

若逆矩阵为 𝑐−1 c−1，可以通过类似操作得到原数：

𝐴 𝑖=𝑛∑𝑗=0 𝑐−1(𝑖,𝑗)𝐹 𝑊 𝑇[𝐴]𝑗 A i=∑j=0 n c−1(i,j)F W T[A]j

逆矩阵不一定存在，比如如果有一排 0 0 或者一列 0 0 那么这个矩阵就没有逆，我们在构造时需要格外小心．

### 按位或

我们可以构造：

[1 0 1 1][1 0 1 1]

这样满足 𝑐(𝑖,𝑗)𝑐(𝑖,𝑘) =𝑐(𝑖,𝑗 ∪𝑘)c(i,j)c(i,k)=c(i,j∪k)．我们发现，这和我们前面推出的 𝐹 𝑊 𝑇[𝐴] =m e r g e(𝐹 𝑊 𝑇[𝐴 0],𝐹 𝑊 𝑇[𝐴 0] +𝐹 𝑊 𝑇[𝐴 1])F W T[A]=merge(F W T[A 0],F W T[A 0]+F W T[A 1]) 一模一样！同理，下面也是一个满足这个条件的矩阵，但我们一般使用上面这个：

[1 1 1 0][1 1 1 0]

虽然下面这个矩阵也满足 𝑐(𝑖,𝑗)𝑐(𝑖,𝑘) =𝑐(𝑖,𝑗 ∪𝑘)c(i,j)c(i,k)=c(i,j∪k)，但这个矩阵存在一排 0 0，不存在逆，所以不合法：

[0 0 1 1][0 0 1 1]

如果我们要进行逆变换，则需要对矩阵求逆，以 最上面 这个矩阵为例，得：

[1 0−1 1][1 0−1 1]

然后按照顺变换的方法，把逆变换矩阵代入即可．

### 按位与

我们可以构造：

[1 1 0 1][1 1 0 1]

这样满足 𝑐(𝑖,𝑗)𝑐(𝑖,𝑘) =𝑐(𝑖,𝑗 ∩𝑘)c(i,j)c(i,k)=c(i,j∩k)．

逆矩阵：

[1−1 0 1][1−1 0 1]

### 按位异或

我们可以构造：

[1 1 1−1][1 1 1−1]

这样满足 𝑐(𝑖,𝑗)𝑐(𝑖,𝑘) =𝑐(𝑖,𝑗 ⊕𝑘)c(i,j)c(i,k)=c(i,j⊕k)．

逆矩阵：

[0.5 0.5 0.5−0.5][0.5 0.5 0.5−0.5]

## FWT 是线性变换

FWT 是线性变换．也就是说，它满足：

𝐹 𝑊 𝑇[𝐴+𝐵]=𝐹 𝑊 𝑇[𝐴]+𝐹 𝑊 𝑇[𝐵]F W T[A+B]=F W T[A]+F W T[B]

以及：

𝐹 𝑊 𝑇[𝑐⋅𝐴]=𝑐⋅𝐹 𝑊 𝑇[𝐴]F W T[c⋅A]=c⋅F W T[A]

## K 维 FWT

其实位运算的本质是对一个 𝑛 n 维 {0,1}{0,1} 向量的运算．或运算就是每一维取 m a x max．且运算就是每一维取 m i n min．异或运算则是每一维对应相加再 m o d 2 mod 2．

位运算有个特点：向量的每一位都是独立的．

我们把 {0,1}{0,1} 扩展到 [0,𝐾) ∩𝐙[0,K)∩Z 也就是扩展到 𝐾 K 进制，看看会得到什么？

### max 运算

我们将 ∪∪ 运算拓展到 𝐾 K 进制，定义 𝑖 ∪𝑗 i∪j 表示按位取 m a x max，有：

𝑐(𝑖,𝑗)𝑐(𝑖,𝑘)=𝑐(𝑖,𝑗∪𝑘)c(i,j)c(i,k)=c(i,j∪k)

若 𝑗 =𝑘 j=k，那么上式又是：

𝑐(𝑖,𝑗)𝑐(𝑖,𝑗)=𝑐(𝑖,𝑗)c(i,j)c(i,j)=c(i,j)

也就是说，每一行的 1 1 必定只能在 0 0 的前面，如果在后面则不合法了．手玩一下可以发现一组合法构造：

⎡⎢ ⎢ ⎢ ⎢⎣1 0 0 0 1 1 0 0 1 1 1 0 1 1 1 1⎤⎥ ⎥ ⎥ ⎥⎦[1 0 0 0 1 1 0 0 1 1 1 0 1 1 1 1]

求逆可得：

⎡⎢ ⎢ ⎢ ⎢⎣1 0 0 0−1 1 0 0 0−1 1 0 0 0−1 1⎤⎥ ⎥ ⎥ ⎥⎦[1 0 0 0−1 1 0 0 0−1 1 0 0 0−1 1]

### min 运算

我们将 ∩∩ 运算拓展到 𝐾 K 进制，定义 𝑖 ∩𝑗 i∩j 表示按位取 m i n min，有：

𝑐(𝑖,𝑗)𝑐(𝑖,𝑘)=𝑐(𝑖,𝑗∩𝑘)c(i,j)c(i,k)=c(i,j∩k)

若 𝑗 =𝑘 j=k，那么上式又是：

𝑐(𝑖,𝑗)𝑐(𝑖,𝑗)=𝑐(𝑖,𝑗)c(i,j)c(i,j)=c(i,j)

也就是说，每一行的 1 1 必定只能在 0 0 的后面，如果在前面则不合法了．手玩一下可以发现一组合法构造：

⎡⎢ ⎢ ⎢ ⎢⎣1 1 1 1 0 1 1 1 0 0 1 1 0 0 0 1⎤⎥ ⎥ ⎥ ⎥⎦[1 1 1 1 0 1 1 1 0 0 1 1 0 0 0 1]

求逆可得：

⎡⎢ ⎢ ⎢ ⎢⎣1−1 0 0 0 1−1 0 0 0 1−1 0 0 0 1⎤⎥ ⎥ ⎥ ⎥⎦[1−1 0 0 0 1−1 0 0 0 1−1 0 0 0 1]

前两者用得比较少，用得比较多的是：

### 不进位加法

我们将 ⊕⊕ 运算拓展到 𝐾 K 进制，定义 𝑖 ⊕𝑗 i⊕j 表示按位相加再 m o d 𝐾 mod K，有：

𝑐(𝑖,𝑗)𝑐(𝑖,𝑘)=𝑐(𝑖,𝑗⊕𝑘)c(i,j)c(i,k)=c(i,j⊕k)

我们构造 𝑐(𝑖,𝑗) =𝜔 𝑗 𝐾 c(i,j)=ω K j，就可以满足要求了：

𝜔 𝑗 𝐾 𝜔 𝑘 𝐾=𝜔 𝑗⊕𝑘 𝐾 ω K j ω K k=ω K j⊕k

但是每一行都一样矩阵也没有逆，所以我们可以构造 𝑐(𝑖,𝑗) =𝜔(𝑖−1)𝑗 𝐾 c(i,j)=ω K(i−1)j 即可．

有下面这个矩阵：

⎡⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢⎣1 1 1⋯1 1 𝜔 1 𝐾 𝜔 2 𝐾⋯𝜔 𝑘−1 𝐾 1 𝜔 2 𝐾 𝜔 4 𝐾⋯𝜔 2(𝑘−1)𝐾 1 𝜔 3 𝐾 𝜔 6 𝐾⋯𝜔 3(𝑘−1)𝐾⋮⋮⋮⋱⋮1 𝜔 𝑘−1 𝐾 𝜔 2(𝑘−1)𝐾⋯𝜔(𝑘−1)(𝑘−1)𝐾⎤⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥⎦[1 1 1⋯1 1 ω K 1 ω K 2⋯ω K k−1 1 ω K 2 ω K 4⋯ω K 2(k−1)1 ω K 3 ω K 6⋯ω K 3(k−1)⋮⋮⋮⋱⋮1 ω K k−1 ω K 2(k−1)⋯ω K(k−1)(k−1)]

此即为 范德蒙德矩阵，求逆可得：

1 𝐾⎡⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢⎣1 1 1⋯1 1 𝜔−1 𝐾 𝜔−2 𝐾⋯𝜔−(𝑘−1)𝐾 1 𝜔−2 𝐾 𝜔−4 𝐾⋯𝜔−2(𝑘−1)𝐾 1 𝜔−3 𝐾 𝜔−6 𝐾⋯𝜔−3(𝑘−1)𝐾⋮⋮⋮⋱⋮1 𝜔−(𝑘−1)𝐾 𝜔−2(𝑘−1)𝐾⋯𝜔−(𝑘−1)(𝑘−1)𝐾⎤⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥⎦1 K[1 1 1⋯1 1 ω K−1 ω K−2⋯ω K−(k−1)1 ω K−2 ω K−4⋯ω K−2(k−1)1 ω K−3 ω K−6⋯ω K−3(k−1)⋮⋮⋮⋱⋮1 ω K−(k−1)ω K−2(k−1)⋯ω K−(k−1)(k−1)]

如果我们题目给出的模数是存在单位根的，我们就可以简单实现．

但是 单位根在模意义下可能不存在，所以我们考虑扩域，就是人为地定义一个 𝑥 x，满足 𝑥 𝐾 =1 x K=1，然后直接把 𝑥 x 代入计算，这样每个数都是一个关于 𝑥 x 的 𝑘 −1 k−1 次多项式．我们只需要在 m o d 𝑥 𝐾−1 mod x K−1 下计算即可．那么矩阵可以这么表示：

⎡⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢⎣1 1 1⋯1 1 𝑥 1 𝑥 2⋯𝑥 𝑘−1 1 𝑥 2 𝑥 4⋯𝑥 2(𝑘−1)1 𝑥 3 𝑥 6⋯𝑥 3(𝑘−1)⋮⋮⋮⋱⋮1 𝑥 𝑘−1 𝑥 2(𝑘−1)⋯𝑥(𝑘−1)(𝑘−1)⎤⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥⎦[1 1 1⋯1 1 x 1 x 2⋯x k−1 1 x 2 x 4⋯x 2(k−1)1 x 3 x 6⋯x 3(k−1)⋮⋮⋮⋱⋮1 x k−1 x 2(k−1)⋯x(k−1)(k−1)]

但是这么做可能会存在零因子，也就是 一个数有多种表示方法，我们无法确定一个数的真实值．

我们考虑不 m o d 𝑥 𝐾−1 mod x K−1 了，我们 m o d mod 分圆多项式 Φ 𝐾(𝑥)Φ K(x)，他满足 𝑥 x 的阶为 𝑘 k，且在 ℚ Q 上不可约．所以我们定义上面的计算是在 m o d Φ 𝐾(𝑥)mod Φ K(x) 下进行即可．

还有一个问题是，m o d Φ 𝐾(𝑥)mod Φ K(x) 常数大（因为 Φ Φ 本身就是一个多项式）．但是因为 Φ 𝐾(𝑥) ∣𝑥 𝑘 −1 Φ K(x)∣x k−1，我们只需要在计算时 m o d 𝑥 𝑘 −1 mod x k−1，最后再 m o d Φ 𝐾(𝑥)mod Φ K(x) 即可．

## 例题

「CF 1103E」Radix sum

给定一个长度为 𝑛 n 的序列 𝑎 1,𝑎 2,...,𝑎 𝑛 a 1,a 2,...,a n，对于每一个 𝑝 ∈[0,𝑛 −1]p∈[0,n−1]，求满足下列条件的整数序列 𝑖 1,𝑖 2,...,𝑖 𝑛 i 1,i 2,...,i n 的方案数，对 2 5 8 2 58 取模：

- ∀𝑗 ∈[1,𝑛],𝑖 𝑗 ∈[1,𝑛]∀j∈[1,n],i j∈[1,n]；
- 𝑛∑𝑗=1 𝑎 𝑖 𝑗 =𝑝∑j=1 n a i j=p，这里的加法定义为十进制不进位加法．

𝑛 ≤1 0 5,𝑎 𝑖 ≤1 0 5 n≤10 5,a i≤10 5

题解

我们可以想到 dp：设计状态 𝑓 𝑖,𝑠 f i,s 表示考虑到第 𝑖 i 个数，当前加法状态为 𝑠 s．因为 FWT 变换是线性的，可以先变换为 FWT 点值表示法，然后变成自己的 𝑛 n 次幂，最后再变换回来．

上面是平凡的，但是题目给出了模数 2 5 8 2 58．发现没有单位根，所以考虑扩域．

这里的分圆多项式 Φ 1 0(𝑥) =𝑥 4 −𝑥 3 +𝑥 2 −𝑥 +1 Φ 10(x)=x 4−x 3+x 2−x+1．

然而我们发现 UFWT 时，需要除去进制 1 0 10，然而我们发现 1 0 10 在 2 5 8 2 58 下没有逆元．实际上我们发现 5 5 在 2 5 8 2 58 下是有逆元的：5 7 6 4 6 0 7 5 2 3 0 3 4 2 3 4 9 57646075230342349，我们只需要再除去一个 2 2 就可以了．设已经除以了 5 5 的答案为 𝑥 x，真正的答案为 𝑦 y，也就是 2 5 𝑦 ≡𝑥(m o d 2 6 4)2 5 y≡x(mod 2 64)，显然，我们有 𝑦 ≡𝑥 2 5(m o d 2 6 4−5)y≡x 2 5(mod 2 64−5)，也就是 𝑦 ≡𝑥 2 5(m o d 2 5 9)y≡x 2 5(mod 2 59)，所以直接将最后的答案除以 2 5 2 5 即可．虽然出题人不知道为什么要模 2 5 8 2 58，但再取下模即可．

【CF103329F】【XXII Opencup, Grand Prix of XiAn】The Struggle

给出一个椭圆 𝐸 E，其中所有整点的坐标均在 [1,4 ⋅1 0 6][1,4⋅10 6] 之间．求 ∑(𝑥,𝑦)∈𝐸(𝑥 ⊕𝑦)3 3 𝑥−2 𝑦−1 m o d 1 0 9 +7∑(x,y)∈E(x⊕y)33 x−2 y−1 mod 10 9+7 的值．

题解

这是一道比较不裸的题，出题人提供了详细的英文题解，具体请见 此链接．

## 参考资料

- 桃酱的算法笔记
- ZnPdCo 的博客

1. 维基百科 ↩

> 本页面最近更新：2026/1/7 08:56:54，更新历史
> 发现错误？想一起完善？ 在 GitHub 上编辑此页！
> 本页面贡献者：Ir1d, Tiphereth-A, ZnPdCo, c-forrest, Enter-tainer, Xeonacid, BinDir0, HeRaNO, lxlonlyn, nocriz, nocrizwang, qkhm, TrisolarisHD, xyf007
> 本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用