うっかりE問題を見てしまい1週間うんうん唸り続ける羽目になったけどようやくなんとなくわかったのでメモ。公式解説のほかいろいろ見た。問題名でググって出てくるとこは大体目を通しましたよと。もはやどれを参考にできたかも覚えておらぬ。

解説の流れ

https://img.atcoder.jp/diverta2019/editorial.pdf

$0,1,..,N+1$ の番号がついた $N$ 個のマスが左から右に向かって並んでいる。マス $i$ には整数 $b_{i}$ が書かれている。すぬけ君ははじめに好きな整数 $X$ を任意に選んだのち、駒をマス $0$ に置く。その後、以下のルールで駒を動かす。

現在駒が置かれているマスより、番号が大きいマスにしか動かせない

現在駒が置かれているマスに $0$ が書かれているなら、 $X$ が書かれているマスに駒を移動させなくてはならない

現在駒が置かれているマスに $X$ が書かれているなら、 $0$ が書かれているマスに駒を移動させなくてはならない

最終的に駒がマス $N$ に置かれているように駒を動かす方法は何通りあるか？

与えられた数列を $A$ 、各要素を $a_{i}, 1\leq i \leq N$ とおく。
$a_{i}$ の累積xorの数列を $B$ 、各要素を $b_{i}, 1\leq i\leq N$ とおく。
与えられた数列を分割して作成した数列を $C_{i}, 1\leq i\leq k$ 、数列 $C_{i}$ の要素を $c_{ij}, 1 \leq j \leq l$ とおく。下図みたいな感じ。
f:id:trsing:20190519135624g:plain

ある値 $X$ で $C_{i}$ たちの美しさが全て等しくなるとする。このとき、

$C_{i}$ の要素に対してxorを取ると $X$ 。
$C_{i}$ に対して累積xorを取ると $C_{1}=b_{d}=X,C_{1}\oplus C_{2}=b_{e}=0,C_{1}\oplus C_{2}\oplus C_{3}=b_{f}=X$ と、 $X,0$ が交互に並ぶ形になる。

$B$ の要素から $X$ と $0$ に注目し、交互に並ぶように選べば美しさが等しい分割となる。
f:id:trsing:20190519160046p:plain

簡単のため $b_{N}$ が $0$ でない場合を考えます。このときは $X$ が一意に定まります。

$\oplus_{i=1}^{k}C_{i}=\oplus_{i=1}^{N}a_{i}=b_{N}$ だから $b_{N}= 0 or X$ 。
$b_{N}\neq0$ なら $X=b_{N}$ と $X$ が一意に定まる。

0/Xの遷移に加え、前の値の代わりに自分の値を使えるということだろう(あまり理解してない)
f:id:trsing:20190519151615p:plain

$X= 0$ の場合は特殊ですが、容易に計算可能です。

値が $0$ の $b_{i}$ の数が $n$ 個とすれば $2^{n-1}$ (単に仕切りをどこにいれるかという話)。

$b$ を $X$ と $0$ 以外の数を取り除いたのち、ランレングス圧縮を行った数列における $0$ の出現回数は $b$ における $X$ の出現回数で抑えられることが重要です。

$0$ は $X$ に隣接していることになるので、圧縮すればせいぜい $X$ の出現数 $+1$

$b_{i}= 0$ なる $i$ に関する遷移をうまく遷移をまとめると

うまくまとめる・・・
f:id:trsing:20190519141517p:plain

ここで詰んだので他の解説やらを探すと次の方のコードおよび解説のおかげでなんとなくわかりました。ありがとうございます。

D：k個の区間の選択を、x[0]=0<x[1]<x[2]<...<x[k-1]<x[k]=Nとなるようなx[1],...,x[k-1]の選択と同一視する。Sを累積xorとして、条件は0=S[x[0]]=S[x[2]]=S[x[4]]=...、S[x[1]]=S[x[3]]=S[x[5]]=...と書ける。
— selpoAC (@selpoAC) 2019年5月11日

Submission #5380934 - diverta 2019 Programming Contest

自分の理解は次のようになります。あってるかどうかは知らぬ。

$dp[j$ ]から $dp[i$ ]への影響は途中にある $0$ の個数による。 f:id:trsing:20190519151656p:plain
漸化式は
$\displaystyle{ dp[i]=1+\sum_{j=0}^{i-1}\left( \sum_{k=j}^{i-1}z[k] \right)dp[j]\\ \hspace{20pt}= 1+\sum_{j=0}^{i-2}\left( \sum_{k=j}^{i-1}z[k] \right)dp[j]+z[i-1]dp[i-1]\\ \hspace{20pt}= 1+\sum_{j=0}^{i-2}\left( \sum_{k=j}^{i-2}z[k] + z[i-1] \right)dp[j]+z[i-1]dp[i-1]\\ \hspace{20pt}= 1+\sum_{j=0}^{i-2}\left( \sum_{k=j}^{i-2}z[k] \right) dp[j]+ z[i-1]\sum_{j=0}^{i-2} dp[j]+z[i-1]dp[i-1]\\ \hspace{20pt}= dp[i-1]+z[i-1]\sum_{j=0}^{i-1} dp[j] }$
※最初の1は初手で $i$ を選ぶ場合