問題一覧 > 通常問題

No.603 hel__world (2)

レベル : / AI推定難易度 : 2500 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 8
作問者 : testestest / テスター : りあん
お気に入りにしたユーザー ProblemId : 1993 / 自分の提出
問題文最終更新日: 2026-06-27 11:05:14
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
Advent Calendar Contest 2017 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。