Codeforces Round #635 (Div. 1) E1. Chiori and Doll Picking (easy version)

E1しか解けていないので、E1しか通らない解法を書きます…。この他にも色々な解法があるっぽい？

問題概要

$n$ 個の非負整数 $a_{1}, ..., a_{n}$ が与えられる。また非負整数 $m$ が与えられ、 $0 \le a_{i} \lt 2^{m}$ である。

$a_{1}, ..., a_{n}$ から任意個の要素を選ぶ選び方は全部で $2^{n}$ 通りある。選んだ要素のXOR和の立っているビット数が $k$ であるような選び方の個数を、 $k=0, ..., m$ の全てに対して $\bmod 998244353$ で求めよ。

制約（E1）

$1 \le n \le 2\times 10^{5}$
$0 \le m \le 35$
$0 \le a_{i} \lt 2^{m}$

解法

初手は掃き出し法

「 $n$ 個の要素から任意個選んでXOR和を取る」という操作を考える上で強力な道具が、 $\mathbb{F}_{2}$ 上での線形代数、特に「掃き出し法」です。このブログでもいくつかの問題で解説を書いています。

各 $a_{i}$ を行、各ビット桁を列とする行列を考え、行基本変形による掃き出し法を行うと、答えを変えないまま以下の性質を満たす行列に変形できます。

ゼロでない行（基底）として残る $a_{i}$ の個数は、ビット桁数以下である。
各ビット桁について、その桁を最上位ビット桁（MSB）とする $a_{i}$ は高々1つである。

ゼロになった要素が $z$ 個ある場合は、それらを無視して計算し、最後に全ての答えに $2^{z}$ を掛ければ良いです。以降は基底となった高々 $(m+1)$ 個の要素について考えます。

MSBで半分全列挙

一番下の桁を $0$ 桁目と書くことにします。 $d$ 桁目は $2^{d}$ に対応する桁です。

E1の制約において最も大きい桁は $35$ 桁目です。ここで $0, ..., 17$ 桁目を「下位ビット」、 $18, ..., 35$ 桁目を「上位ビット」と呼ぶことにします。

この解法のアイデアとしては、基底を

グループ $0$ ：MSBが上位ビットであるもの
グループ $1$ ：MSBが下位ビットであるもの

の2グループに分けて半分全列挙をします。「各桁をMSBとする $a_{i}$ は高々1つである」という性質により、両方のグループの要素数は18個以下です。またグループ $1$ の上位ビットは全て $0$ です。

重要な視点は、グループ $0$ の列挙結果とグループ $1$ の列挙結果をマージする際に上位ビットが干渉することはない、ということです。つまりグループ $0$ について全列挙した時点で、上位の具体的なビット列は忘れてしまって立っている個数だけを保持しておけば良い、ということが言えます。

具体的には全列挙によって以下の値を集計することになります。

$n_{0}\lbrack u \rbrack\lbrack B \rbrack =$ グループ $0$ の基底の選び方のうち、そのXOR和において上位ビットの立っている個数が $u$ で、下位ビット列が $B$ であるものの個数
$n_{1}\lbrack B \rbrack =$ グループ $1$ の基底の選び方のうち、そのXOR和において下位ビット列が $B$ であるものの個数

各 $u=0, ..., 18$ について別々に、 $n_{0}\lbrack u \rbrack\lbrack B \rbrack$ と $n_{1}\lbrack B \rbrack$ をマージします。これは $\oplus$ をXOR演算の記号として

$\displaystyle n\lbrack u \rbrack\lbrack B \rbrack = \sum_{B_{0}\oplus B_{1}=B} (n_{0}\lbrack u \rbrack\lbrack B_{0} \rbrack \times n_{1}\lbrack B_{1} \rbrack)$

となるような数列 $\displaystyle n\lbrack u \rbrack$ を求めることになり、俗に添字XOR畳み込みと呼ばれています。これは「高速アダマール変換」と呼ばれるもので計算できます。

色々な畳み込み - kazuma8128’s blog

これが計算できれば、 $\displaystyle n\lbrack u \rbrack\lbrack B \rbrack$ を $ans\lbrack u+p(B)\rbrack$ に足し込んでいけば良いです。ここで $p(B)$ はビット列 $B$ の立っているビットの個数、 $ans$ は答えとなる数列を表すことにします。