高速ウォルシュ変換（FWT）と高速メビウス変換（FMT）

  • FWT高速ウォルシュ変換学習ノート

初見では理解困難ですが、そのコードの簡潔さには感銘を受けます。覚えるしかないかもしれません。

基本的な変換式

[FWT(A) = (FWT(A_0), FWT(A_1 + A_0)) ][IFWT(A) = (IFWT(A_0), IFWT(A_1 - A_0)) ]と

[FWT(A) = (FWT(A_0 + A_1), FWT(A_1)) ][IFWT(A) = (IFWT(A_0 - A_1), IFWT(A_1)) ]論理和

[FWT(A) = (FWT(A_0 + A_1), FWT(A_0 - A_1)) ][IFWT(A) = (IFWT(\frac{A_0 + A_1}{2}), IFWT(\frac{A_0 - A_1}{2})) ]排他的論理和

コード実装

記憶のコツ

すべてを暗記する必要はなく、効果的な覚え方があります

論理和の場合

論理和演算では、値が大きくなる傾向があります。そのため、上位ビットの値に下位ビットの値を加算します。（少し分かりにくいですね）

論理積の場合

論理積は論理和とは逆に、値が小さくなる傾向があります。そのため、下位ビットの値に上位ビットの値を加算します。（さらに分かりにくくなりましたね）

排他的論理和

少し特殊ですか？FFTに似ていますね。その形式で覚えましょう...

IFWT

IFWTは、単にFWTを元に戻す操作です。

前に何かを加算した位置があり、その値はまだ変わっていない（大霧）ので、その値を減算すれば元に戻ります。

（排他的論理和の場合）以前の値が分からない？心配ありません。方程式を立てて解くことができます（大霧）

注意点！！

  • FWTは長さを倍にする必要はなく、バタフライ変換も不要です
  • FWT内ではできるだけ<=比較を使用するのが安全です。十分なメモリがあれば問題ありません。特に一点：limitを選択する際はwhile (limit <= n)!! この時は必ず以下比較を使用してください。そうしないと不完全になります！！
  • その他の注意点はNTT内の注意点と同様です

補足説明

論理和畳み積：（\(FWT:f[] -> f'[]\))

[f'[i]=\sum_{j|i=i}f[j] ]\(f'[i]\)が\(i\)の部分集合の重み和であることがわかります。したがって、P3175 [HAOI2015]ビット単位の論理和のような部分集合問題を解くことができます。

部分集合畳み込み

P6097 【テンプレート】部分集合畳み込み

\(a, b\)配列が与えられます。次のように定義します：

[c_k = \sum_{iandj=0,iorj=k}a_i * b_j ]つまり、\(k\)の中から互いに素な部分集合\(i,j\)を見つけ、\(a_i * b_j\)の総和を計算します

互いに素という制約がなければ、これはFWT_ORの典型問題です。互いに素という制約を追加するには、単に\(|i| + |j| = |k|\)という制約を追加すればよいです。

したがって、\(|i|,|j|,|k|\)を列挙し、サイズが\(|i|,|j|\)のすべての\(|a_i|,|b_j|\)の総和をまとめて乗算し、\(c_k\)に加算し、その後\(c\)配列を畳み戻せば答えとなります。

理論的背景

論理和畳み込み

高次元プレフィックス和配列を定義します：

[\hat f_S = \sum_{T\subseteq S}f_T ]この畳み込みが論理和畳み込みの性質を持つことがわかります：

[\hat h_S = \sum_{T \subseteq S} h_T][=\sum_{T \subseteq S} \sum_{A|B = T} f_Ag_B ][=\sum_{A \subseteq S} \sum_{B \subseteq S}f_A g_B ][= \hat f_A \hat g_B ]これにより、\(O(n)\)の乗算が可能になります。（\(n\)は総状態数、または\(2^{|U|}\)です）

\(\hat f(S)\)をどのように計算するか？高次元プレフィックス和の方法を使用できます（for(次元i） for (すべての状態S) S += S - i)、ここで\(S - i\)は特別な判定が必要です。計算量は\(O(nlogn)\)です。したがって、\(S\)中の\(i\)の両側の次元を直接列挙することで、定数を1/2に減らすことができます。

論理積畳み込み

類似の高次元プレフィックス和配列を定義します：

[\hat f_S = \sum_{S\subseteq T}f_T ]この配列は論理積畳み込みの性質を持ちます：

[\hat h(S) = \sum_{S \subseteq T} h(T)][=\sum_{S \subseteq T} \sum_{A andB = T} f_Ag_B ][= \sum_{T, A, B}f_Ag_B[S \subseteq T][A and B = T] ][=\sum_{A} \sum_{B}f_A g_B[S \subseteq A and B] ][=\sum_{S \subseteq A} \sum_{S \subseteq B} f_Ag_B ][= \hat f_A \hat g_B ]コード実装は逆（0を1、1を0として見なす）にして高次元プレフィックス和を一度行うだけです。

排他的論理和畳み込み

これはFMTを使用できません。

プレフィックス和ではない補助配列を定義します：

[\hat f_S = \sum_{T}(-1)^{|S &amp; T|}f_T ]そして、その畳み込みの性質を探します：

[\hat h_S = \sum_{T}(-1)^{|S &amp; T|}h_T ][= \sum_{T}\sum_{A \wedge B=T}(-1)^{|S &amp; T|} f_A g_B ][=\sum_{A, B}(-1)^{|S &amp; (A \wedge B)|}f_Ag_B ]これ以上展開できないように見えますか？\(|S \& (A \wedge B)|\)という式と\(|S \& A| + |S \& B|\)の関係について考えてみましょう。

ビット単位に分解して寄与を考える（これは明らかに可能です）まず、\(S\)に現れないビットを除外し、\(S\)に現れるビットを考えます。もし\(a = b\)なら、\(a \wedge b = 0\)、元の式への寄与は0、後の式への寄与は偶数、したがって等価です。もし\(a \not= b\)なら、\(a \wedge b = 1\)、元の式への寄与は1、後の式への寄与も1です。

驚くべき発見：\((-1)^{|S \& (A \wedge B)|} = (-1)^{|S \& A| + |S \& B|}\)、したがって展続けられます：

[\hat h_S = \sum_{A, B}(-1)^{|S &amp; A|} f_A (-1)^{|S &amp; B|} g_B ][=\hat f_A \hat g_B ]これにより、排他的論理和畳み積を高速に計算できます。

しかし、この\(\hat f(S)\)をどうやって計算しますか？高次元プレフィックス和をもう一度使うのでしょうか。実際にはDFTを模倣することができます、奇数と偶数に分けて分割統治で議論します。

1次元ずつ考えます。初期状態（自分自身のみ）では、\(\hat f(S) = (-1)^{|0 \& 0|}f(S) = f(S)\)です。現在の次元（最上位ビット）が0のグループ（左側のグループ）については、その値は元の左側の対応する\(\hat f\)値（\(|0S \& 0S|=|S|\)のため）に元の右側の対応する\(\hat f\)値（\(|0S \& 1S|=|S|\)のため）を加えたものです。現在の次元（最上位ビット）が1のグループ（右側）については、その値は元の右側の対応する\(\hat f\)値の負の値（\(|1S \& 1S| = |S| + 1\)のため、右側と右側のANDのみが+1）に左側の対応する\(\hat f\)値（\(|1S \& 0S|=|S|\)のため）を加えたものです。計算量：\(O(nlogn)\)

そして逆変換です。実際には次の式もあります：

[f_S = \frac{1}{2^n} \sum_T (-1)^{|S &amp; T|} \hat f_T ]これも証明しやすいです。\(\hat f_T\)を展開し、和の順序を交換すれば：

[right = 1/2^n \sum_{P}f_P\sum_{T}(-1)^{|S &amp; T| + |P &amp; T|} ]右上の式はおなじみのものです：\(|(S \wedge P) \& T|\)、したがって：

[right = 1/2^n \sum_{P}f_P\sum_{T}(-1)^{|(S \wedge P) &amp; T|} ]重要なのは次を証明することです：

[\sum_{T \subseteq U} (-1)^{|T &amp; Q|} = 2^n[Q=\phi] ]これは\(Q\)のどれかの次元に値がある場合、その次元を押さえて\(T\)をその次元を持つものと持たないものに分けると、両クラスの数は同じで、奇偶性が異なる一対一の対応関係があるため、式は0になってしまいます。

そうすればあとはすべて簡単です。ここでは証明を省略します。

そしてこの\(\frac{1}{2^n} \sum_T (-1)^{|S \& T|} \hat f_T\)も計算しやすいです。もう一度FWTを行い、最後に\(1/2^n\)で割るだけです（または各層で2で割る）

（実際、最も簡単な方法は何をしたかを「元に戻す」ことで、直接ウォルシュ逆変換を導き出すことです）。

まとめ

  • 論理和：

[\hat f_S = \sum_{T \subseteq S} f_T ]意味：（高次元プレフィックス和と同様）\(S\)のすべての部分集合の和。

  • 論理積：

[\hat f_S = \sum_{S \subseteq T} f_T ]意味：\(S\)を含むすべての集合の和。

  • 排他的論理和：

[\hat f_S = \sum_{T}(-1)^{|S &amp; T|}f_T ]意味：?????

応用問題

Hard Nim (4589)

クラシックなNimゲーム（交互に石を取り、操作不能者が負け）。

n個の山があり、各山の石の初期数はm以下の素数です。

先手必敗局面の数を求めてください。

n <= 1e9, m <= 5e4

最も素朴な方法は、各方案を列挙し、それが合法かどうかを判断することです。

[\sum_{i=1}^{m}\sum_{j=1}^{m}\sum_{k=1}^m...(nsigma)...\sum_{l=1}^m[i,j,k,...,l=prime,ixorjxorkxor~...xorl=0] ]計算量：O(\(nm^n\))

2つのsigma（n=2）の場合は：

[\sum_{i=1}^m\sum_{j=1}^m[i,j=prime,ixorj=0] ]つまり

[\sum_{ixorj=0}{[i,j=prime]} ]これは排他的論理和畳み込みの形式です。

FFT関連のカウント問題の経験から、重み配列を使用できます。つまり、\(a[i]\)が排他的論理和値\(i\)の場合の数を表します。そしてFWTを使用できます。

類似した累乗の方法で、\(a[]\)を\(x\)として見なし、多項式累乗を行い、最終的な答えは\(a[0]\)となります。計算量はおおよそ\(O(mlogm~logn\))（少し不安？）

多項式累乗に思い至ると、我々は大きな道に迷い込み、計算量さえ保証できなくなります。FFT、NTT、FWTが点値表現を利用して加速するという本質を忘れないでください。点値表現に変換した後も、交換法則、結合法則などをサポートしているため、各点値を直接累乗できます。計算量\(O(mlogm+mlogn)\)

\(コード:\)

limit = 1;
while (limit <= m)	limit <<= 1;
for (int i = 0; i <= m; ++i)	data[i] = (!is_prime[i]);
FWT_xor(data, 1);
for (int i = 0; i <= limit; ++i)	data[i] = fast_pow(data[i], n);
FWT_xor(data, -1);
printf("%lld\n", data[0]);

Binary Table (CF662C)

問題解説 CF662C 【Binary Table】を参照してください。

n行m列のテーブルがあり、各要素は0/1です。操作では行または列を選択し、0/1を反転できます（0を1に、1を0に）。いくつかの操作の後、テーブル内の1の最小数を求めてください。

\(n<=20, m<=1e5\)

行の反転状況をStateとして列挙します。最初のi列の状況を\(S_i\)とすると、各\(State\)について、答えは（\(F_s\)が列状態sの最大寄与（1の数）を表す）：

[\sum_{i=1}^m{F_{StatexorS_i}} ]列挙対象を変換： 行操作後の列状態X（\(F_X\)を直接使用して答えを統計するため）と\(S_i\)（\(Q_s\)が状態Sの列の数を表す）を列挙します：

[\sum_{X=0}^{2^n}\sum_{S = 0}^{2^n}{[StatexorS = X]F_{X}* Q_{S}} ]少し変形します：

[\sum_{X=0}^{2^n}\sum_{S = 0}^{2^n}{[State = XxorS]F_{X}* Q_{S}} ]つまり：

[\sum_{XxorS=State}{F_X * Q_S} ]そしてFとQを事前計算し、FWTを使用すればよいです。

練習問題

P3175 [HAOI2015]ビット単位の論理和

A国の貿易

FWTテンプレート（デバッグ用）

inline void FWT_or(long long *arr, int mode) {
	for (int i = 1; i < limit; i <<= 1) {
		for (int j = 0; j < limit; j += (i << 1)) {
			for (int p = 0; p < i; ++p) {
				arr[i + j + p] = (arr[i + j + p] + arr[j + p] * mode) % MOD;
				if (arr[i + j + p] < 0)	arr[i + j + p] += MOD;
			}
		}
	}
}

inline void solve_or() {
	memcpy(temp1, inputA, sizeof(inputA));
	memcpy(temp2, inputB, sizeof(inputB));
	FWT_or(temp1, 1); FWT_or(temp2, 1);
	for (int i = 0; i < limit; ++i)	outputC[i] = temp1[i] * temp2[i] % MOD;
	FWT_or(outputC, -1);
	for (int i = 0; i < limit; ++i)	printf("%lld ", outputC[i]);
	puts("");
}

inline void FWT_and(long long *arr, int mode) {
	for (int i = 1; i < limit; i <<= 1) {
		for (int j = 0; j < limit; j += (i << 1)) {
			for (int p = 0; p < i; ++p) {
				arr[j + p] = (arr[j + p] + arr[i + j + p] * mode) % MOD;
				if (arr[j + p] < 0)	arr[j + p] += MOD;
			}
		}
	}
}

inline void solve_and() {
	memcpy(temp1, inputA, sizeof(inputA));
	memcpy(temp2, inputB, sizeof(inputB));
	FWT_and(temp1, 1); FWT_and(temp2, 1);
	for (int i = 0; i < limit; ++i)	outputC[i] = temp1[i] * temp2[i] % MOD;
	FWT_and(outputC, -1);
	for (int i = 0; i < limit; ++i)	printf("%lld ", outputC[i]);
	puts("");
}

inline void FWT_xor(long long *arr, int mode) {
	for (int i = 1; i < limit; i <<= 1) {
		for (int j = 0; j < limit; j += (i << 1)) {
			for (int p = 0; p < i; ++p) {
				long long nx = arr[j + p], ny = arr[i + j + p];
				arr[j + p] = (nx + ny) % MOD;
				arr[i + j + p] = (nx - ny + MOD) % MOD;
				if (mode == -1) {
					arr[j + p] = arr[j + p] * inv2 % MOD;
					arr[i + j + p] = arr[i + j + p] * inv2 % MOD;
				}
			}
		}
	}
}

inline void solve_xor() {
	memcpy(temp1, inputA, sizeof(inputA));
	memcpy(temp2, inputB, sizeof(inputB));
	FWT_xor(temp1, 1); FWT_xor(temp2, 1);
	for (int i = 0; i < limit; ++i)	outputC[i] = temp1[i] * temp2[i] % MOD;
	FWT_xor(outputC, -1);
	for (int i = 0; i < limit; ++i)	printf("%lld ", outputC[i]);
	puts("");
}

タグ: ウォルシュ変換 メビウス変換 畳み込み アルゴリズム 高速フーリエ変換

6月1日 17:44 投稿

ホットタグ

©2026 異端開発室