問題一覧 > 通常問題

No.1654 Binary Compression

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

問題文

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

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

入力

$S$

  • $1\leq |S|\leq 3\times 10^6$
  • $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もしくは右上の雲マークをクリックしてアカウントを作成してください。