CodeChef CHEFFILT

はじめに

この問題を本番中解いていた時に，$O(4^W)$から$O(2^W)$に落とせることに気づいて面白かったのでメモ．ぶっちゃけ気づいたのは，提出前に手元でテストしててDPの表を出力してみたからで，完全に偶然だったりする．

問題

参照

https://www.codechef.com/DEC15/problems/CHEFFILT

要約

$S~(0 \leq S < 2^W-1)$ と $n~(1 \leq n \leq 100,000)$ 個の数列$F_i(1 \leq i \leq n, 0 \leq F_i < 2^W)$ が与えられる．$F_i$ の部分集合のうち全要素の xor を取った結果が $S$ となるものの個数を$1,000,000,007$で割った余りを求めよ．（$F$ には重複した値が含まれるが，異なるものとして扱う）

想定解法

参照

https://discuss.codechef.com/questions/77624/cheffilt-editorial

要約

$F_i$ に含まれる相違なる値は $2^W$ 個以下である．そこで，$F$ 中で値が $x$ である要素の個数を $C(x)~(0 \leq x < 2^W)$とおく．

同じ値同士の xor は0(すなわち $x \mathrel{\mbox{xor}} x = 0$) であることから，ある値 $x$ が $k$ 個存在する場合，

偶数個を集合に含めた場合は，含めない場合と同じ結果
奇数個を集合に含めた場合は，$x$ 以外の全ビット列と $x$ の xor を取ったものが結果

となる．ここで，($k$ 個のものの中から偶数個選ぶ選び方）＝($k$ 個のものの中から奇数個選ぶ選び方）＝$2^{k-1}$ であることに注意すると，以下のDPを考えることができる．

$D(x, y) := $ $F$ で $x$ 以下の値のみからなる部分集合のうち，その全要素の xor が $y$ となるものの個数．

$$ D(x, y) = \begin{cases} D(x - 1, y) & C(x) = 0 \\ (D(x - 1, y) + D(x - 1, y \mathrel{\mbox{xor}} x)) \cdot 2^{C(x)-1} & C(x) > 0 \\ \end{cases} $$

この解法の計算量は $O(4^W)$ となる．

O(2^w) 解法

実は以下の性質が成り立つ．

任意の $y$ について，$D(x, y) \neq 0$ ならばその値は $x$ によって一意に定まる $$ D(x, y) = \begin{cases} 0 & D(x, y) = 0 \\ E(x) & D(x, y) \neq 0 \\ \end{cases} $$
$E(x)$ は $D(x - 1, x)$ の値から一意に計算可能 $$ E(x) = \begin{cases} E(x - 1) \cdot 2^{C(x)-1} & D(x - 1, x) = 0 \\ E(x - 1) \cdot 2^{C(x)} & D(x - 1, x) \neq 0 \end{cases} $$
$E(x)$の構成手順から，解は $D(2^W-1, S)=0$ ならば0, そうでなければ $2^{n-m}$．ただし，$m$は$D(x, x - 1) \neq 0$ なる $x$ の個数．

補題

$$ \begin{cases} D(x - 1, x) = 0 \wedge D(x - 1, y) \neq 0 \Rightarrow D(x - 1, y \mathrel{\mbox{xor}} x) = 0 \\ D(x - 1, x) \neq 0 \wedge D(x - 1, y) \neq 0 \Rightarrow D(x - 1, y \mathrel{\mbox{xor}} x) \neq 0 \end{cases} $$

補題の証明

$D(x - 1, x) = 0 \wedge D(x - 1, y) \neq 0 \wedge D(x - 1, y \mathrel{\mbox{xor}} x) \neq 0$ となる $y$ が存在すると仮定する．このとき，全要素の xor が $y$ になる集合の1つを $U$ ，$y \mathrel{\mbox{xor}} x$ になる集合を $V$ とおくと，$V$ から共通集合 $U \cap V$ を取り除き差集合 $U \setminus V$ を加えた集合の全要素のxorは $x$ となるため，矛盾する．$D(x - 1, x) \neq 0 \wedge D(x - 1, y) \neq 0 \Rightarrow D(x - 1, y \mathrel{\mbox{xor}} x) \neq 0$も同様に示せる．

証明

$x=0$ のとき， $D(0, 0) = 2^{C(0)}$ かつ $D(0, y) = 0~(y \neq 0)$ なので，成り立つ($E(0)=2^{C(0)}$)

$x-1$のとき，成り立つと仮定すると，$x$のとき，

$D(x - 1, x)=0$ならば，補題から，$D(x - 1, y) \neq 0$ なる $y$ について，$D(x - 1, y \mathrel{\mbox{xor}} x) = 0$であり，$y \neq z \Rightarrow y \mathrel{\mbox{xor}} x \neq z \mathrel{\mbox{xor}} x$であることから， $$ D(x, y \mathrel{\mbox{xor}} x) = D(x, y) = D(x - 1, y) \cdot 2^{C(x)-1} = E(x-1) \cdot 2^{C(x)-1} $$ であり，$y$ および $y \mathrel{\mbox{xor}} x$ 以外の値 $z$ については $D(x, z) = 0$ となる．
$D(x - 1, x)\neq0$ならば，補題から，$D(x - 1, y) \neq 0$ なる $y$ について，$D(x - 1, y \mathrel{\mbox{xor}} x) = E(x - 1)$であり， $$ D(x, y) = (D(x - 1, y) + D(x - 1, y \mathrel{\mbox{xor}} x)) \cdot 2^{C(x)-1} = E(x-1) \cdot 2^{C(x)} $$ であり，$y$ 以外の値 $z$ については $D(x, z) = 0$ となる．

以上から，$x$のときにも性質1,2が成り立つことがわかる．

性質3は，実際に$E$の漸化式を展開してみるとわかる．

実装

重要なのは$D(x, y) > 0$かどうかだけであり，個数は独立して計算できるので，$D(x, y) > 0$かどうかを $2^W$ の配列$A$で管理する．これで，$D(x - 1, x) > 0$かどうかを$O(1)$で判定できる．さらに，$D(x, y) > 0$ なる $y$ の集合をリスト$B$でも管理しておく．$D(x, x - 1) = 0$となった場合，リスト$B$の各要素$y$について$y \mathrel{\mbox{xor}} x$ を計算し，$A$および$B$を更新する．$D(x, y) > 0$ なる $y$ の集合は更新のたびに2倍になるため，更新は高々 $\log 2^W=W$ 回しか発生せず，$i$回目の更新の段階におけるリストの要素数は$2^i$のため，全体の計算量は$O(2^W)$

ソースコード

from collections import Counter
from sys import stdin
_data = iter(stdin.read().split('\n'))
input = lambda: next(_data)
MOD = 1000000007
L = 10
for _ in range(int(input())):
    s = int(input().replace('b', '0').replace('w', '1'), 2)
    n = int(input())
    ct = Counter(int(input().replace('-', '0').replace('+', '1'), 2)
                for _ in range(n))
    g = [False] * 2**L
    g[s] = True
    m = 0
    for f, x in ct.items():
        if not g[f ^ s]:
            for i in range(2**L):
                if g[i]: g[i ^ f] = True
            m += 1
    print(pow(2, n - m, MOD) if g[0] else 0)

追記

Editorialページのコメントに上がっていたのだけど，Gauss Jordan 使えば$O(\min(n, 2^W) \cdot W^2)$になるらしい．行空間の基底を求める問題に帰着できるっぽい？