Prefix XORs - AtCoder Regular Contest 137 D

AtCoder Regular Contest 137 D - Prefix XORs の解法です．コンテスト中に解いた方法 (実験結果から適当に求める) をベースに，公式解説を参照して追加しました．リュカの定理の証明もWikipediaを見て書きました．

問題概要

長さ$N$の整数列 $A = (A_1, \ldots, A_N)$ と整数 $M$ が与えられる．下の操作を$k$回行ったあとの $A_i$ の値を $A(i, k)$ と書くことにする． $k = 1, 2, \ldots, M$ について，$A(N, k)$ を求めよ．

操作: 各$i = 1, 2, \ldots, N$ について， $A_i$ を同時に $A_1 \oplus A_2 \oplus \cdots \oplus A_i$ で置き換える．

制約: $1 \leq N, M \leq 10^6$; $0 \leq A_i < 2^{30}$

問題へのリンク

解法

実験

$A(i, k)$ は，$A_1, \ldots, A_i$ のいくつかのXORをとったものになる．そこで，$a(i, m, k) \in \{0, 1\}$ をとって， $A(i, k) = \bigoplus_{m=1}^{i} a(i,m,k) A_m$ と書く．計算してみると分かるとおり，$a(i, m, k)$ は，$i - m$ と $k$ にしか依存しない．そこで，$b(j, k) := a(j, 0, k)$ と書くことにする． $A(i, k) = \bigoplus_{m=1}^{i} b(i - m, k) A_m = \bigoplus \{ A_{i - j} \mid b(j, k) = 1; j = 0, \ldots, i-1 \}$ だから，各 $k = 1, 2, \ldots, M$ について，$b(j, k) = 1$ となる $j$ を (高速に) 列挙できれば良い．

計算してみると，$b(j, k)$ は次のようになっている:

   0 11111111111111111111111111111111
   1 10101010101010101010101010101010
  10 11001100110011001100110011001100
  11 10001000100010001000100010001000
 100 11110000111100001111000011110000
 101 10100000101000001010000010100000
 110 11000000110000001100000011000000
 111 10000000100000001000000010000000
1000 11111111000000001111111100000000
1001 10101010000000001010101000000000
1010 11001100000000001100110000000000
1011 10001000000000001000100000000000
1100 11110000000000001111000000000000

左端は，k - 1 の値の2進表示．スペースの直後が j = 0 の値, その次が j = 1 の値，その次が j = 2 の値，… である．

たとえば，$k - 1 = 6 = 110_2$ のとき，$b(k, j) = 1$ となる$j$ は， $0, 1, 8, 9, 16, 17, 24, 25, \ldots$ であり，2進表記では次のようになる:

(下から) 2ビット目と3ビット目は 0 であり，他のビットは任意に取れる．0 に固定されているビットは，$k - 1 = 110_2$ の立っているビットである．他の$k$についても，すべてそのような関係が成立している．つまり， $\newcommand{\band}{\;\&\;} b(j, k) = 1 \iff j \band (k-1) = 0$ である (&は，ビットごとの AND)．

証明

帰納法でも証明できるような気がするが，公式解説に従ってリュカの定理を使う．

リュカの定理

$p$ を素数，$m$, $n$ を非負整数とする． $m$ と $n$ を $p$進法で表記して $m = m_k p^k + m_{k-1} p^{k-1} + \cdots + m_1 p + m_0$， $n = n_k p^k + n_{k-1} p^{k-1} + \cdots + n_1 p + n_0$ とするとき， $$ \binom{m}{n} \equiv \prod_{i=0}^{k} \binom{m_i}{n_i} \qquad (\text{mod } p)$$ である．ただし，$x < y$ のとき，$\binom{x}{y} = 0$ とする．

リュカの定理の証明 (Wikipedia)

$|M| = m$ なる集合 $M$ をとり，このサイズ $n$ の部分集合の数を mod p で求めれば良い． $M$ を，$m_k$ 個のサイズ $p^k$ の部分集合，…，$m_0$ 個のサイズ1の部分集合に分割する．分割した各部分を円環状に並べておく．置換 $\pi: M \to M$ を，$\pi(x)$ を，自分が属する円環の右隣の要素，として定義する． $N \subseteq M$, $|N| = n$ となる $N$ を考える．サイズ $p^i$ の円環で，$N$ の要素と $M\setminus N$ の要素の両方を含むものがあったとする．そのような最大の $i$ をとると，

$N, \pi(N), \pi^2(N), \ldots, \pi^{p^i - 1}(N)$ は全て異なる．
これらのうち一つを $N’$ とすると， $\{N, \pi(N), \ldots, \pi^{p^i - 1}(N)\}$ と $\{N’, \pi(N’), \ldots, \pi^{p^i - 1}(N’)\}$ は，集合として一致する．

したがって，そのような $N$ の個数は $p$ の倍数である．ゆえに，$\binom{m}{n}$ は，いくつかの円環の和で表せるようなサイズ$n$の部分集合の個数と mod p で等しい．サイズが $n$ になるように選ぶためには，サイズ$p^k$ の円環を $n_k$ 個，$\ldots$，サイズ1の円環を$n_0$個，それぞれ選ぶ必要がある． (終)

$b(j, k) = 1 \iff j \band (k - 1) = 0$ の証明

$b$ の計算方法を見れば， $b(j, k) \equiv \binom{j + k - 1}{j}\quad(\text{mod} 2)$ であることが分かる．したがって，リュカの定理によって，$b(j, k) = 0$ となるための条件は， $j$ の2進表記が 1 で，$j + k-1$ の2進表記が 0 となるような桁が存在することであり，これは，$j$と $k-1$ の2進表記がともに1となる桁が存在することと同値である． (終)

計算方法

高速ゼータ変換の要領で計算する．具体的には以下の通り:

$M$ のビット長を $L$ とする．$k \in\{ 1, 2, \ldots, M\}$ であった． $t \in \{0, 1, \ldots, L\}$ とし， $j \in \{0, 1, \ldots, N-1 \}$に対し， $j \sim^t k$ を，次の条件が成り立つこととして定義する:

第0ビットから第$t - 1$ ビットまでは，$j$ と $k-1$ の両方が1になることはない．
第$t$ビットから第$L-1$ビットまでは，$j$ と $k-1$ は一致する．

$f(t, k)$ を，$\oplus \{ A_{N - j} \mid j \sim^{t} k;\; j = 0, \ldots, 2^L - 1\}$ で定義する．定義より， $f(L, k)$ が求める $A(N, k)$ である．

これは，次のように計算できる．

$f(0, k) = \oplus \{ A_{N - j} \mid j \band (2^L - 1) = k - 1 \}$
$k \band 2^t \neq 0$ のとき: $f(t + 1, k) = f(t, k \band (\sim 2^t))$
$k \band 2^t = 0$ のとき: $f(t + 1, k) = f(t, k) \oplus f(t, k \;|\; 2^t)$

実装

主要部分:

int main() {

  ll N, M; cin >> N >> M;
  vector<ll> A(N);
  REP(i, N) cin >> A[i];
  ll L = 64 - __builtin_clzll(M);
  vector<ll> vec(1LL << L);
  REP(j, N) vec[j & ((1LL << L) - 1)] ^= A[N-1 - j];
  REP(t, L) {
    REP(k, 1LL << L) {
      if (k >> t & 1) continue;
      ll k0 = k;
      ll k1 = k | (1LL << t);
      ll v0 = vec[k0];
      ll v1 = vec[k1];
      vec[k0] = v0 ^ v1;
      vec[k1] = v0;
    }
  }
  REP(k, M) cout << vec[k] << " ";
  cout << endl;
  return 0;
}

全体: 提出 #30396276

問題概要#

解法#

実験#

証明#

リュカの定理#

リュカの定理の証明 (Wikipedia)#

$b(j, k) = 1 \iff j \band (k - 1) = 0$ の証明#

計算方法#

実装#

問題概要

解法

実験

証明

リュカの定理

リュカの定理の証明 (Wikipedia)

$b(j, k) = 1 \iff j \band (k - 1) = 0$ の証明

計算方法

実装