問題一覧 > 通常問題

No.603 hel__world (2)

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 13
作問者 : testestesttestestest / テスター : りあんりあん
0 ProblemId : 1993 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2018-03-10 02:13:32

Note

この問題は No.295 hel__world を及びその想定解を元に作成されましたが、この出題により誤りの箇所が見つかりNo.295の問題文自体も修正されました。
(2017/12/03 02:50)問題文を修正いたしました。ご迷惑をおかけしました。

問題文

文字列$S$の連結成分の個数を、次の操作を行えるだけ行った後の文字列長さとして定めます。
操作:同じ文字が2文字以上連続する箇所があれば、そこから1文字取り除く
例えば「helloworld」の連結成分の個数は$9$、「aababbaaa」の連結成分の個数は$5$となります。

文字列 $S$ の $T$ 数を $S$ が含む部分列 $T$ の個数とします。
例えば、$S$ をhelloworld、$T$ をhelworld とすると、helloworldはhel__worldとhe_l_worldの2つを部分列として持つので、helloworld の helworld 数は $2$ です。

次の2条件を満たす文字列$S$に対する、$T$数の最大値を$\mod 10^6+3$で求めてください。
・$S$に含まれる文字$alpha$の個数は高々$S_{alpha}$
・$S$の連結成分の個数と$T$の連結成分の個数は等しい
条件を満たすような文字列が存在しなければ0を出力してください。

入力

$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}$ は、文字列 $S$ に文字 $alpha$ が 高々 $S_{alpha}$ 個含まれていることを表す。
文字列 $S$,$T$が含む文字は、$a,b,\cdots,z$(小文字のアルファベット)のいずれかである。

出力

条件をみたすような$S$に対する最大の $T$ 数を$\mod 10^6+3$で出力してください。(10^6+3は素数です)
最後に改行してください。

サンプル

サンプル1
入力
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
出力
4

$S$ をhellwoorldとするとhelworld数は 4 でこの時最大になります。

サンプル2
入力
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
出力
6

helllooのhello数は 6 でこの時最大になります。

サンプル3
入力
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
出力
64250

条件に合うような文字列に対するT数の最大値は 27315825477537795403677696 なのでmod 10^6+3では64250になります。

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