結果

問題 No.603 hel__world (2)
ユーザー gew1fw
提出日時 2025-06-12 14:47:43
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,154 bytes
コンパイル時間 198 ms
コンパイル使用メモリ 82,560 KB
実行使用メモリ 240,556 KB
最終ジャッジ日時 2025-06-12 14:51:00
合計ジャッジ時間 5,394 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 14 WA * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 10**6 + 3

# Precompute factorial and inverse factorial modulo MOD
fact = [1] * MOD
for i in range(1, MOD):
    fact[i] = fact[i-1] * i % MOD

inv_fact = [1] * MOD
inv_fact[MOD-1] = pow(fact[MOD-1], MOD-2, MOD)
for i in range(MOD-2, -1, -1):
    inv_fact[i] = inv_fact[i+1] * (i+1) % MOD

def compress(s):
    if not s:
        return [], []
    res_char = []
    res_count = []
    current = s[0]
    cnt = 1
    for c in s[1:]:
        if c == current:
            cnt += 1
        else:
            res_char.append(current)
            res_count.append(cnt)
            current = c
            cnt = 1
    res_char.append(current)
    res_count.append(cnt)
    return res_char, res_count

# Read input
s_counts = list(map(int, input().split()))
S = {chr(ord('a') + i): s_counts[i] for i in range(26)}
T = input().strip()

# Compress T
C, t_list = compress(T)

# Check if S can have the same compressed string as C
# Also, group components by character
from collections import defaultdict

char_groups = defaultdict(list)  # key: char, value: list of t_i in order
for c, t in zip(C, t_list):
    char_groups[c].append(t)

# Check for each character in C if S has enough count for sum(t_i)
total_product = 1

for c in C:
    if c not in char_groups:
        print(0)
        exit()

for c, components in char_groups.items():
    sum_t = sum(components)
    available = S[c]
    if sum_t > available:
        print(0)
        exit()
    x_total = available - sum_t
    k = len(components)
    if k == 0:
        continue
    # Distribute x_total into k components
    base = x_total // k
    rem = x_total % k
    for i in range(len(components)):
        t_i = components[i]
        x_i = base
        if i < rem:
            x_i += 1
        m_i = t_i + x_i
        # Compute comb(m_i, t_i) mod MOD
        n_mod = m_i % MOD
        if n_mod < t_i:
            print(0)
            exit()
        # Compute comb(n_mod, t_i)
        numerator = fact[n_mod]
        denominator = inv_fact[t_i] * inv_fact[n_mod - t_i] % MOD
        comb_val = numerator * denominator % MOD
        total_product = total_product * comb_val % MOD

print(total_product)
0