atcoder#AGC022E. [AGC022E] Median Replace
[AGC022E] Median Replace
配点 : 点
問題文
タイチは、0
と 1
からなる奇数長 の文字列 は次の条件を満たすとき 美しい と考えています。条件:次の操作を 回行って、最終的な文字列の唯一の文字を 1
にすることができる。
- の 連続する つのビットを選び、それらの中央値でそれらを置き換える。例えば、
00110
の中央の ビットに操作を適用すると、この文字列は010
となる。
タイチは 0
、1
、?
からなる文字列を持っています。この文字列の ?
をそれぞれ 1
か 0
に置き換える方法であって、美しい文字列が得られるものの個数を で割った余りをタイチは知りたいです。
制約
- は奇数である。
- のすべての文字は
0
、1
、?
のいずれかである。
入力
入力は標準入力から以下の形式で与えられる。
出力
?
を置き換える方法であって、美しい文字列が得られるものの個数を で割った余りを出力せよ。
1??00
2
?
を 0
か 1
で置き換える方法は以下の 通りあります。
11100
: この文字列は美しいです。なぜなら、まず最後の ビットに操作を適用して110
とし、次に文字列全体に操作を適用すると1
となるからです。11000
: この文字列は美しいです。なぜなら、まず最後の ビットに操作を適用して110
とし、次に文字列全体に操作を適用すると1
となるからです。10100
: この文字列は美しくありません。なぜなら、最終的に文字列が1
となるような操作手順が存在しないからです。10000
: この文字列は美しくありません。なぜなら、最終的に文字列が1
となるような操作手順が存在しないからです。
よって、美しい文字列を得る方法は 通りです。
?
1
この場合、1
が唯一の美しい文字列です。
?0101???10???00?1???????????????0????????????1????0
402589311
答えを で割った余りを出力することを忘れずに。