No.1694 ZerOne
タグ : / 解いたユーザー数 69
作問者 :
eSeF
/ テスター :
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 of0s contained in $u$. - (3): The number of
1s contained in $t$ is equal to the number of1s contained in $u$.
Input
$S$
[Constraints]
- $S$ is a string consisting of
0and1with 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もしくは右上の雲マークをクリックしてアカウントを作成してください。