差分
このページの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 | ||
|---|---|---|---|
| 行 164: | 行 164: | ||
| 先述の通り、$X$ は一意に確定する。末尾の $X$ へは $DP[X][N][0]$ から遷移するので、それが答え。 | 先述の通り、$X$ は一意に確定する。末尾の $X$ へは $DP[X][N][0]$ から遷移するので、それが答え。 | ||
| - | 末尾が $X$ だから見るべきは $DP[X][N][X]$ じゃないのか、と一瞬思うが、最後は必ず区間を確定するので、遷移元である0の方を見る。 | + | 末尾が $X$ だから見るべきは $DP[X][N][X]$ じゃないのかと一瞬思うが、これはあくまで「最後に決定した区間が |
| - | + | ||
| - | $acc$ 上で最後に出現した0の後に | + | |
| - | + | ||
| - | $DP[X][N][X]$ は、そのような使えない | + | |
| 累積xor | 累積xor | ||
| ~~~~ ~ ←末尾は必ず使う | ~~~~ ~ ←末尾は必ず使う | ||
| - | └こいつらを使ったら、末尾との間に0がもう1つないといけないので使用不可 | + | └DP[X][N][X]は、これとかで終わったまま |
| - | →DP[X][N][X]はこいつら(や、もっと前のX)で終わるパターンも含んでしまっている | + | 末尾では区間未確定なパターンも含まれる |
| ===累積xorの末尾が0だった場合=== | ===累積xorの末尾が0だった場合=== | ||
