差分
このページの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]$ じゃないのかと一瞬思うが、これはあくまで「最後に決定した区間が $X$ であるもの」の数。$acc$ の末尾は必ず区間として確定しなければならないが、$DP[X][N][X]$ にはその前の $X$ で確定したまま末尾で未確定状態の場合も含まれる。$DP[X][N][0]$ であれば、最後に確定した 0 から必ず末尾の $X$ に遷移できる。 |
| - | $acc$ 上で最後に出現した0の後に $X$ が複数個あろうが、条件を満たすようにするには末尾の $X$ 以外は使えない。 | + | |
| + | ~~~~ ~ ←末尾は必ず使う | ||
| + | └DP[X][N][X]は、これとかで終わったまま | ||
| + | | ||
| - | $DP[X][N][X]$ は、そのような使えない $X$ も混ざった値となってしまっている。 | + | ===accの末尾が0だった場合=== |
| - | + | ||
| - | 累積xor | + | |
| - | ~~~~ ~ ←末尾は必ず使う | + | |
| - | └こいつらを使ったら、末尾との間に0がもう1つないといけないので使用不可 | + | |
| - | | + | |
| - | + | ||
| - | ===累積xorの末尾が0だった場合=== | + | |
| まず、$X=0$ の場合、$acc_i$ が0の時に区切るか区切らないかを（末尾以外）独立に選べるので、$2^{0の出現回数-1}$ である。 | まず、$X=0$ の場合、$acc_i$ が0の時に区切るか区切らないかを（末尾以外）独立に選べるので、$2^{0の出現回数-1}$ である。 | ||
