AtCoder Regular Contest 156 D問題メモ

AtCoder Regular Contest 156

D - Xor Sum 5

問題

長さ $N$ の数列 $A=(A_1,...,A_N)$
長さ $K$ 、各要素 $1 \le X_i \le N$ の数列 $X=(X_1,...,X_K)$ に対し、 $f(X)$ を以下で定義する
- $f(X)=A_{X1}+A_{X2}+...+A_{XK}$
$X$ としてあり得る数列は $N^K$ 通りあるが、それら全てについての $f(X)$ の総XORを求めよ
$1 \le N \le 1000$
$0 \le A_i \le 1000$
$1 \le K \le 10^{12}$

解法

考慮すべき $X$ の個数がとんでもない数になりそうだが、実は多くはXORで打ち消しあって消える。
合計が同じになる、要素を並び替えただけの2つの $X$ 同士は打ち消しあうため、考慮しなくてよい。

たとえば $K=11$ 個から、 $A_1$ を $3$ 個、 $A_3$ を $4$ 個、 $A_5$ を $4$ 個選ぶような $X$ の個数は、多項係数 $\dfrac{11!}{3! \times 4! \times 4!}$ で求められる。
これが偶数になるような選び方は考慮しなくてよいことになる。
また、奇数の時も打ち消しあって残った1個のみ考慮すればよい。

では、奇数になるのはどんなとき？
これは、Lucasの定理を使える。

Lucasの定理とその証明 | 高校数学の美しい物語

特にmod2、nCr の偶奇を知りたいときは、以下が成り立つ。

nCr は奇数 ⇔ $n\&r=r$ 、つまり $r$ を2進数表記したときに立っているbitは、 $n$ でも全て立っている

今回の場合もこれを連鎖的に適用すると、以下が成り立つ。

$\dfrac{K!}{r_1!r_2!...r_m!}$ が奇数
⇔ $r_1,r_2,...,r_m$ が、どの2つもどのbitも重複していない（ $r_i\&r_j=0$ ）、かつ総和が $K$

これを言い換えると（なかなか直感的には言い換えるのが難しく思うが）、
「 $K$ の2進数表記で立っているbitごとに、 $A_1～A_N$ のどれかから選んでbitshiftして足し合わせる」ような操作で作られる数が、並べ替えの個数が奇数となるような $X$ に対する $f(X)$ となる。

K = 1011            ※K,Aiは2進数表記
A = (10, 11, 101)

    1の位    10の位      1000の位       f(X)   加算するAiの内訳
o-- + 10 --- + 10*0 --- + 10*000   →  10110   10を11個
|       |          |--- + 11*000   →  11110   10を 3個、 11を 8個
|       |          `--- +101*000   → 101110   10を 3個、101を 8個
|       |--- + 11*0 --- + 10*000   →  11000   10を 9個、 11を 2個
|       |          |--- + 11*000   → 100000   10を 1個、 11を10個
|       |          `--- +101*000   → 110000   10を 1個、 11を 2個、101を 8個
|       `--- +101*0 --- ...
|                  |--- ...
|-- + 11 --- ...
`-- +101 --- ...
                                      ~~~~~~ 答えは、ここに来る全f(X)のXOR

答えを求める際には、この樹形図を縦に見て、下の桁から確定させていく。

1の位で答えの下1桁を求めたら、10や1000の位ではもう変化しないので、確定する。

「 $A_i$ の下1桁のXORが1」かつ「 $N$ が奇数」の場合に限り、答えの下1桁は1となる。
- この後、樹形図に従い各枝はそれぞれ等しく $N$ の(残り枝分かれ回数)乗倍されるが、そもそもXORが0なら、何倍しても0
- $N$ が偶数の場合、最後の枝（上例では1000の位）以外は、「 $N$ の○乗倍」が偶数となり、打ち消し合うため

次、10の位を考慮するにあたり、繰り上がりが発生する。
「10からは1」「11からは1」「101からは10」繰り上がるが、「1」繰り上がる2つに関しては、この後の樹形図が同じため打ち消し合う。
したがって、「10」のみが残る。繰り上がる数も、奇数個繰り上がるもののみを持っておけばよい。

10の位では、繰り上がってきた数それぞれに対して、各 $A_i$ を加算した集合（上例では100,101,111）で同様に下1桁のXORを計算し、答えに反映する。

100の位では、 $K$ でbitが立っていないため、（ $A_i$ は加算せず）繰り上がってきた数の集合のままで下1桁のXORを計算する。
（ $K$ で立っているbitを予め調べ、10の位とまとめて求めてもよい）

1000の位でも同様に、各繰り上がった数に各 $A_i$ を足す。
最後については下1桁でなく、 $A_i$ 加算後の集合のそのままの値のXORを求め、bitshiftして答えに加算する。
最後は、 $N$ が偶数でも加算してよい。
これで最終的な答えとなる。

各桁で繰り上がる数の種類数の上限は、 $\dfrac{A_{max}}{2} \simeq 500$ 。
それぞれに $N$ 個の $A_i$ の加算を試す、ということを最大 $O(\log{K})$ 回おこなうため、計算量は $O(NA_{max}\log{K})$ 。

Python3