問題一覧 > 通常問題

No.1694 ZerOne

レベル : / AI推定難易度 : 1700 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 69
作問者 : eSeF / テスター : chineristAC ygussany
お気に入りにしたユーザー ProblemId : 5360 / 自分の提出
問題文最終更新日: 2021-09-29 17:46:11
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 316 (順位表) の他の問題:

Problem Statement

You are given a string $S$ consisting of 0 and 1. Find the number of distinct strings that can be obtained by repeating the following operation $0$ or more times.

  • Choose two non-empty contiguous substrings $t$ and $u$ of $S$ satisfying the following conditions (1), (2), (3), and swap their positions in $S$.
    • (1): $t$ and $u$ are taken without overlapping. That is, if $t$ is the $L_t$-th through $R_t$-th characters of $S$ and $u$ is the $L_u$-th through $R_u$-th characters of $S$, then $L_t\le R_t < L_u\le R_u$ must hold.
    • (2): The number of 0s contained in $t$ is equal to the number of 0s contained in $u$.
    • (3): The number of 1s contained in $t$ is equal to the number of 1s contained in $u$.

Input

$S$

[Constraints]

  • $S$ is a string consisting of 0 and 1 with length between $1$ and $60$, inclusive.

Output

Print on one line the number of strings that can possibly be obtained by performing the operation $0$ or more times.

Sample

Sample 1
Input
001010
Output
2

For example, if we choose $t=$ 001 (characters 1~3) and $u=$ 010 (characters 4~6) and swap their positions, the string becomes 010001.

In fact, no strings other than this one and the initial string can be generated, so the answer is 2.

Note that if we take $t=$ 010 (characters 2~4) and $u=$ 010 (characters 4~6), the numbers of 0 and 1 are equal, but the 4th character of $S$ is contained in both, so (1) is not satisfied and the operation is invalid.

Sample 2
Input
10
Output
1

There is no pair of strings that can be chosen as $t$ and $u$, so no operation can be performed.

Sample 3
Input
010101
Output
3

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