問題一覧 > 通常問題

No.1654 Binary Compression

レベル : / AI推定難易度 : 2900 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 24
作問者 : chocorusk / テスター : ygussany
お気に入りにしたユーザー ProblemId : 6632 / 自分の提出
問題文最終更新日: 2021-08-09 09:32:41
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 310 (順位表) の他の問題:

Problem Statement

Rusk has a string $S$ consisting only of 0 and 1. He can perform the following operation any number of times.

  • Choose $2$ adjacent characters of $S$ and delete the digit that is not the larger one.
How many strings can be obtained as $S$ after performing the operation $0$ or more times, as many times as he likes? Find the count modulo $924844033$ (a prime).

Input

$S$

  • $1\leq |S|\leq 3\times 10^6$
  • Each character of $S$ is 0 or 1.

Output

Output the number of possible strings $S$ after the operations, modulo $924844033$.

Sample

Sample 1
Input
00101
Output
9

The possible strings $S$ after the operations are the following $9$: 1, 01, 11, 001, 011, 101, 0011, 0101, 00101. For example, 01 can be obtained by performing the operations as follows.

  • Choose the $1$st and $2$nd characters of $S$ and delete the $1$st character. $S$ becomes 0101.
  • Choose the $2$nd and $3$rd characters of $S$ and delete the $3$rd character. $S$ becomes 011.
  • Choose the $2$nd and $3$rd characters of $S$ and delete the $2$nd character. $S$ becomes 01.

Sample 2
Input
1111
Output
4

Sample 3
Input
1001001001001001001001001001001001001001001001001001001001001
Output
605956436

Output the answer modulo $924844033$.

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