No.603 hel__world (2)
タグ : / 解いたユーザー数 8
作問者 :
testestest
/ テスター :
りあん
Note
This problem was created based on No.295 hel__world and its intended solution, but this problem revealed an error, and the statement of No.295 itself was also corrected.(2017/12/03 02:50) The problem statement has been corrected. We apologize for the inconvenience.
Problem Statement
The number of connected components of a string $S$ is defined as the length of the string after performing the following operation as many times as possible.Operation: if there is a place where the same character appears two or more times consecutively, remove one character from it
For example, the number of connected components of "helloworld" is $9$, and that of "aababbaaa" is $5$.
The $T$ count of a string $S$ is the number of subsequences $T$ contained in $S$.
For example, let $S$ be helloworld and $T$ be helworld. Since helloworld has the two subsequences hel__world and he_l_world, the helworld count of helloworld is $2$.
Find the maximum $T$ count over strings $S$ satisfying the following two conditions, $\mod 10^6+3$.
・The number of occurrences of the character $alpha$ in $S$ is at most $S_{alpha}$
・The number of connected components of $S$ equals the number of connected components of $T$
If no string satisfies the conditions, output 0.
Input
$S_a$ $S_b$ $S_c$ $S_d$ $S_e$ $S_f$ $S_g$ $S_h$ $S_i$ $S_j$ $S_k$ $S_l$ $S_m$ $S_n$ $S_o$ $S_p$ $S_q$ $S_r$ $S_s$ $S_t$ $S_u$ $S_v$ $S_w$ $S_x$ $S_y$ $S_z$ $T$
$0 \le S_{alpha} \le 10^{18}$ ( $alpha \in \{a,\cdots, z\}$)
$1 \le |T| \le 10^6$
$S_{alpha}$ means that the string $S$ contains at most $S_{alpha}$ occurrences of the character $alpha$.
The strings $S$,$T$ contain only the characters $a,b,\cdots,z$ (lowercase letters).
Output
Output the maximum $T$ count over strings $S$ satisfying the conditions, $\mod 10^6+3$. (10^6+3 is prime)
Print a newline at the end.
Sample
Sample 1
Input
0 0 0 1 1 0 0 1 0 0 0 3 0 0 2 0 0 1 0 0 0 0 1 0 0 0 helworld
Output
4
If $S$ is hellwoorld, the helworld count is 4, which is the maximum.
Sample 2
Input
0 0 0 1 1 0 0 1 0 0 0 3 0 0 2 0 0 1 0 0 0 0 1 0 0 0 hello
Output
6
The hello count of hellloo is 6, which is the maximum.
Sample 3
Input
100 100 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 abababababababababababababababab
Output
64250
The maximum T count over strings satisfying the conditions is 27315825477537795403677696, so the answer mod 10^6+3 is 64250.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。