CS Academy: Random Nim Generator
アダマール変換のことはよく分からないので、基本的な線形代数で説明します。
問題概要
0..K の値を持つサイズ N の数列のうち xor の総和が 0 より大きくなるものは何通りあるか。
- $1 \le N \le 20000$
- $1 \le K \le 50000$
解法
$K$ が小さければ行列累乗 DP ができるが、$K$ があまりにも大きい。
この DP の遷移行列はある特徴があって以下のような形になっている。
$$ A = \begin{pmatrix} X & Y \\ Y & X \end{pmatrix} $$
$X,\;Y$ もこの形になっていて、もっと小さいサイズでもこの形になっている。このような行列は対角化が簡単にできて次のようになる。
$$ A= \begin{pmatrix} X & Y \\ Y & X \end{pmatrix}= \frac{1}{n} H_n \begin{pmatrix} J(X)+J(Y) & 0 \\ 0 & J(X)-J(Y) \end{pmatrix} H_n $$
ここで $J(X)$ は行列 $X$ のジョルダン標準形で、$H_n$ は $n$ 次のアダマール行列である。$n$ 次のアダマール行列は次のように再帰的に定義される。
$$ H_1 = \begin{pmatrix} 1 \end{pmatrix}, \quad
H_{2n}=\begin{pmatrix}
H_{n} & H_{n} \\\
H_{n} & -H_{n}
\end{pmatrix}
$$
このように対角化できることは帰納的に示せる。面白いことに、対角化をすることで $A \mathbb{v}$ の計算量が $O(n\log n)$ に落ちる。
アダマール行列とベクトルの積 $H_n \mathbb{v}$
$$ H_{2n} \mathbb{v} =\begin{pmatrix} H_{n} & H_{n} \\ H_{n} & -H_{n} \end{pmatrix} \begin{pmatrix} x \\ y \end{pmatrix} $$
これを計算するには $H_n x$ と $H_n y$ を計算すればいい。$T(n)$ を $H_n x$ を計算する時間とすると $T(n)=2T(n/2)+O(n)$ なので $T(n)=O(n\log n)$ である。
ジョルダン標準形 $J(A)$
$J(A)$ は次のように再帰的に計算できる。
$$ J\left( \begin{pmatrix} X & Y \\ Y & X \end{pmatrix} \right) = \begin{pmatrix} J(X)+J(Y) & O \\ O & J(X)-J(Y) \end{pmatrix} $$
この計算量もまた $O(n \log n)$ である。
対角行列とベクトルの積は $O(n)$ で計算できるので全体の計算量は $O(n \log n)$ である。
アダマール変換
ここまで分かれば問題は解けるのだが、もう一歩先ヘ進んでアダマール変換という概念に繋げる。
「アダマール行列とベクトルの積を求めるコード」と「ジョルダン標準形を求めるコード」は書いてみると分かるが全く同じになる。
このことを考えると、A の 1 行目のベクトルを $u$、dp のベクトルを $v$ とすると次のようにも書ける。
$$ H^{-1} (H u) \circ (H v) $$
ただし$A \circ B$ はアダマール積を表す。$H$ を掛けるというのがアダマール変換である。$H^{-1}=H/n$ なので（ほぼ）直交変換になっている。
アダマール変換と xor 畳み込み
ひとつ前の数式と、そもそもの計算の意味を考えると次の等式が成り立つことが分かる。
$$ H(u \ast v) = (H u) \circ (H v) $$
$u \ast v$ は次のような xor の畳み込みを表す。
for i in range(m): for j in range(n): uv[i^j]=u[i]*v[j]
ということで、アダマール変換という概念を用いてこの問題を解くのであれば以下の式から一発である。
$$ H(\underbrace{u \ast \cdots \ast u}_{n} \ast v) =\underbrace{(Hu)\circ\cdots\circ(Hu)}_{n}\circ (Hv) $$
mod をとっても支障がないのは原理から明らか。
ほとんど同じような問題を以前解いたことがあったので瞬殺だった。アダマール変換は調べてもよく分からなかったので、間違ってたらごめんなさい。
類題。 Problem - 662C - Codeforces
2016/08/25: アダマール変換のコードを inplace アルゴリズムに書き換えた。アダマール変換時に mod を取ってないため再利用時は注意が必要かも。
