問題一覧 > 通常問題

No.1654 Binary Compression

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 24
作問者 : chocorusk / テスター : 👑 ygussany
4 ProblemId : 6632 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-08-09 09:32:41

問題文

ラスク君は0と1のみからなる文字列 S を持っています。ラスク君は次の操作を何回でも行うことができます。

  • S の隣り合う 2 文字を選び、大きくない方の数字を削除する。
操作を 0 回以上好きなだけ行った結果の S として考えられるものは何通りあるでしょうか。924844033 (素数) で割った余りを求めてください。

入力

S

  • 1≤|S|≤3×106
  • S の各文字は0または1である。

出力

操作後の S としてありうるものが何通りあるかを 924844033 で割った余りを出力してください。

サンプル

サンプル1
入力
00101
出力
9

操作後の S としてありうるものは、1, 01, 11, 001, 011, 101, 0011, 0101, 00101 の 9 通りです。 例えば、01 は次のように操作を行うと得られます。

  • S の 1 文字目と 2 文字目を選び、1 文字目を削除する。S は0101となる。
  • S の 2 文字目と 3 文字目を選び、3 文字目を削除する。S は011となる。
  • S の 2 文字目と 3 文字目を選び、2 文字目を削除する。S は01となる。

サンプル2
入力
1111
出力
4

サンプル3
入力
1001001001001001001001001001001001001001001001001001001001001
出力
605956436

924844033 で割った余りを出力してください。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。