差分
このページの2つのバージョン間の差分を表示します。
| 両方とも前のリビジョン前のリビジョン | |||
| 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$ に遷移できる。 | ||
| - | | + | |
| - | ~~~~ ~ ←末尾は必ず使う | + | ~~~~ ~ ←末尾は必ず使う |
| - | └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}$ である。 | ||
