差分

この文書の現在のバージョンと選択したバージョンの差分を表示します。

この比較画面にリンクする

両方とも前のリビジョン 前のリビジョン
programming_algorithm:contest_history:atcoder:2019:0511_diverta2019 [2019/05/16]
ikatakos [解法]
programming_algorithm:contest_history:atcoder:2019:0511_diverta2019 [2019/05/16] (現在)
ikatakos [解法]
ライン 166: ライン 166:
 末尾が $X$ だから見るべきは $DP[X][N][X]$ じゃないのかと一瞬思うが、これはあくまで「最後に決定した区間が $X$ であるもの」の数。$acc$ の末尾は必ず区間として確定しなければならないが、$DP[X][N][X]$ にはその前の $X$ で確定したまま末尾で未確定状態の場合も含まれる。$DP[X][N][0]$ であれば、最後に確定した 0 から必ず末尾の $X$ に遷移できる。 末尾が $X$ だから見るべきは $DP[X][N][X]$ じゃないのかと一瞬思うが、これはあくまで「最後に決定した区間が $X$ であるもの」の数。$acc$ の末尾は必ず区間として確定しなければならないが、$DP[X][N][X]$ にはその前の $X$ で確定したまま末尾で未確定状態の場合も含まれる。$DP[X][N][0]$ であれば、最後に確定した 0 から必ず末尾の $X$ に遷移できる。
  
-  ​累積xor ​ ​X ​ 0  1  ...  0  X  X  2  X +  ​acc  ​X ​ 0  1  ...  0  X  X  2  X 
-                            ~~~~     ~ ←末尾は必ず使う +                        ~~~~     ~ ←末尾は必ず使う 
-                            └DP[X][N][X]は、これとかで終わったまま +                        └DP[X][N][X]は、これとかで終わったまま 
-                              末尾では区間未確定なパターンも含まれる+                          末尾では区間未確定なパターンも含まれる
  
-===累積xorの末尾が0だった場合===+===accの末尾が0だった場合===
  
 まず、$X=0$ の場合、$acc_i$ が0の時に区切るか区切らないかを(末尾以外)独立に選べるので、$2^{0の出現回数-1}$ である。 まず、$X=0$ の場合、$acc_i$ が0の時に区切るか区切らないかを(末尾以外)独立に選べるので、$2^{0の出現回数-1}$ である。
programming_algorithm/contest_history/atcoder/2019/0511_diverta2019.txt · 最終更新: 2019/05/16 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0