diverta 2019 Programming Contest: E - XOR Partitioning

solution.txt

diverta 2019 Programming Contest: E - XOR Partitioning
https://atcoder.jp/contests/diverta2019/tasks/diverta2019_e

思考過程のメモ

## 観察

validな分け方の例を一つ考える。

```
|===|===|===|====|
  a   a   a   a
```

区間のXORがすべて a ならば、最初からの累積和を考えると a, 0, a, 0 ... となっている。
逆にこれ以外のパターンはありうるだろうか？無さそう。
a, 0, a, 0, ... , a,  b (b != a, b != 0) のとき、b XOR a は 明らかに a とは異なる。

## 答えの一歩手前

さて、どうすればこの問題が解けるか。累積和で出現するのが 2^20-1 までなので、

f(i) := 区間が全て i となるような数列の区切り方

としたときに、

`sum(i=0 to 2^20-1) f(i) `

が答えになる。ここで、各 f(i) が armotized で O(1) で求まれば勝利。
ちなみに、まだこの方針で行けるかどうかは分からない。もし行き詰まったら、適宜戻ろう。
戻ったときは、別の「答えの一歩手前」を考える。

## 部分問題1: f(a)

考えたい累積和は a, 0, a, 0 ... の形なので、これを O(|累積和にaが出現する数|) ぐらいで求めたい。
まず特殊なケースとして、a = 0 の場合を考える。

### 部分問題1-1: a = 0

途中に出現する 0 となる仕切りを入れるか入れないか、なので
答えは 2^(0の出現数) 通り。当然全区間のXORが 0 でないと 0 なので注意。これはまた別に場合分けが必要か。

### 部分問題1-2: a != 0

dp[i] := i番目に出現する a の位置までで(区間が全て a となるように)分割する場合の数

### 部分問題1-2-1: a と a の間に出現する0の数

0の出現数の累積和を持てば O(1) で計算できる。


### 部分問題1-2-2: dp[i]

「貰う」形にする。以降、位置x を x番目に出現する a の位置と定義する。

```
dp[i] = 1
        + dp[1] * (位置1から位置i まで出現する0の数)
        + dp[2] * (位置2から位置i まで出現する0の数)
        ...
        + dp[i-1] * (位置i-1から位置i まで出現する0の数)
```

dp[i] にかかる係数が階段状になっているので、次のindexとの差分を考えてみる。
だいたいこのあたりで解けるのを確信する。

```
dp[i+1] = 1
        + dp[1] * (位置1から位置i+1 まで出現する0の数)
        + dp[2] * (位置2から位置i+1 まで出現する0の数)
        ...
        + dp[i-1] * (位置i-1から位置i+1 まで出現する0の数)
        + dp[i-1] * (位置iから位置i+1 まで出現する0の数)
```

各係数は、位置iから位置i+1に出現する0の数だけ増加する。
よって、これまでのdp[i] の合計を求めておけば計算できそう。

### 部分問題1-2-2-1: 全体の累積和が 0 のとき

最終的に累積和が 0 になるのだから、dp[1]〜dp[aの数] の和が答え。
(各状態から最後までの区間を取ると、その区間はaになる)

### 部分問題1-2-2-1: 全体の累積和が s (!= 0) のとき

もちろん、s = a　以外の場合は答えは 0。
そうでない場合は、dp[aの数] がそのまま答え。

## 提出コード

https://atcoder.jp/contests/diverta2019/submissions/9550448