Codeforces Global Round 2 - H. Triple

難問

概要

n$n$ 個のタプル (ai,bi,ci)$(a_i,b_i,c_i)$ が与えられる。各要素は 2k$2^k$ 以下である
各タプルはそれぞれ一つの配列に対応し、その配列に値が ai,bi,ci$a_i,b_i,c_i$ である要素が x,y,z$x,y,z$個あることを表す。
n個の配列から一つずつ要素を選び、そのxorをとる操作をすべての組み合わせについて行ったとき、 0∼2k−1$0\sim 2^k-1$ までの各 i$i$ について、最終的なxorがi$i$になるものの個数を求めよ。

制約

1≤n≤105$1\le n\le {10}^5$
1≤x,y,z≤109$1\le x,y,z\le {10}^9$
1≤k≤17$1\le k\le 17$
0≤ai,bi,ci<2k$0\le a_i,b_i,c_i<2^k$

解法

高速ウォルシュアダマール変換（FWT）をします。FWTについては↓の記事の一番下にあります。
kazuma8128.hatenablog.com

n回FWTをして、変換後に総積をとってから逆変換（IFWT）をすることで解くことができます。
オーダーは全体でO(nk2k)$O(nk{2}^k)$ になります。　終わりです。

全然間に合わないので高速化することを考えます。すべてをFWTするのは無理です。一方で、IFWTは最後に一度だけしか行いません。
また、明らかに3要素しかないものをFWTしているのは効率が悪いので、別の方法を考えます。

ここで、変数を減らすことを考えます。 a′i=0,b′i=ai⊕bi,c′i=ai⊕ci$a_i^{\prime }=0,b_i^{\prime }=a_i\oplus b_i,c_i^{\prime }=a_i\oplus c_i$ と変数変換をしても、最終的な結果に ai$a_i$ の総xorをとることで元の問題の結果も求められることに注目します。以降ではこの変換を行なった後の問題について考えます。

ところで、FWTとはどのような変換になっているのでしょうか。k回目のループについては以下の図のようになります。緑の矢印は係数が+1であること、赤の矢印は係数が-1であることを表しています。

k番目のループの様子

また、変換前のある要素 i$i$ に着目すると、以下のような図を描くことができます。
i=0$i=0$のとき

i = 0

i=6$i=6$のとき

i = 6

この図をじっと眺めると、変換前の各要素は変換後のすべての要素に+1倍または-1倍されて足しこまれることがわかります。また、変換前の0は変換後すべてに+1倍されていることもわかります。より一般化すると、変換前後のインデックスがそれぞれ i,j$i,j$のとき、 (−1)popcount(i&j)$(-1{)}^{popcount(i\mathrm{\&}j)}$ 倍された値が足されていることがわかります。

したがって、ある1つのタプルに注目したとき、変換後の配列の要素は x+y+z,x+y−z,x−y+z,x−y−z$x+y+z,x+y-z,x-y+z,x-y-z$ のいずれかであることがわかります。

変換後のあるインデックス j$j$ を固定して考えたとき、 x+y+z,x+y−z,x−y+z,x−y−z$x+y+z,x+y-z,x-y+z,x-y-z$ の出現回数をそれぞれ p,q,s,t$p,q,s,t$とおくと、p,q,s,t$p,q,s,t$を求めることで変換したものの積を間接的に求めることができます。
具体的には、 j$j$ 番目の要素は (x+y+z)p×(x+y−z)q×(x−y+z)s×(x−y−z)t$(x+y+z{)}^p\times (x+y-z{)}^q\times (x-y+z{)}^s\times (x-y-z{)}^t$ であり、これは繰り返し二乗法を用いることで高速に求められます。

したがって、元の問題は 2k$2^k$ 箇所について p,q,s,t$p,q,s,t$を求める問題に帰着されました。
ところで、n個のタプルについてまとめて変換することを考えます。実際に x,y,z$x,y,z$ に適当な値を入れてFWTをすることで、 (x+y+z)×p+(x+y−z)×q+(x−y+z)×s+(x−y−z)×t$(x+y+z)\times p+(x+y-z)\times q+(x-y+z)\times s+(x-y-z)\times t$ の値が得られます。これは p,q,s,t$p,q,s,t$を変数とする単純な4元1次方程式になっているので、線型独立な基底を4つ選ぶことができれば解くことができます。しかし、行列

⎛⎝⎜⎜⎜1 1 1 111−1−11−11−1⎞⎠⎟⎟⎟$$\left(\begin{array}{ccc}1& 1& 1\\ 1& 1& -1\\ 1& -1& 1\\ 1& -1& -1\end{array}\right)$$

のランクは明らかに3以下であり、線型独立な基底を4つ選ぶことができません。

ここで、（かなり唐突ですが） di=bi⊕ci$d_i=b_i\oplus c_i$ なる要素を考え、その要素が w$w$ 個存在していた場合の問題を考えます。この問題は元の問題の一般化となっており、また w=0$w=0$とすれば元の問題と一致します。 このとき変換後の配列の要素はどうなるでしょうか。
実は、 x+y+z+w,x+y−z−w,x−y+z−w,x−y−z+w$x+y+z+w,x+y-z-w,x-y+z-w,x-y-z+w$ のいずれかになることが容易に示せます（ bi,ci$b_i,c_i$ のbit表現に注目し、両方のbitが立っている、片方だけ立っている、両方立っていない場合を考えると示すことができます）。
また、

⎛⎝⎜⎜⎜1 1 1 111−1−11−11−11−1−11⎞⎠⎟⎟⎟$$\left(\begin{array}{cccc}1& 1& 1& 1\\ 1& 1& -1& -1\\ 1& -1& 1& -1\\ 1& -1& -1& 1\end{array}\right)$$

をwolframalphaになげてみると、正則行列であることが確認できます。
www.wolframalpha.com

したがって線型独立な基底を4つ、たとえば(1,0,0,0),(0,1,0,0),(0,0,1,0),(0,0,0,1)などを (x,y,z,w)$(x,y,z,w)$に実際に当てはめてFWTを行い、得られた4つの式について連立4元1次方程式を解くことで各 j$j$ についてp,q,s,t$p,q,s,t$を求めることができます。

あとは与えられた x,y,z$x,y,z$ の値を用いて (x+y+z)p×(x+y−z)q×(x−y+z)s×(x−y−z)t$(x+y+z{)}^p\times (x+y-z{)}^q\times (x-y+z{)}^s\times (x-y-z{)}^t$の値を求め、IFWTを行うことで元の問題を解くことができました。