結果

問題 No.603 hel__world (2)
ユーザー zimphazimpha
提出日時 2017-12-03 03:18:03
言語 Python2
(2.7.18)
結果
AC  
実行時間 978 ms / 3,000 ms
コード長 2,642 bytes
コンパイル時間 425 ms
コンパイル使用メモリ 7,168 KB
実行使用メモリ 71,284 KB
最終ジャッジ日時 2024-11-30 20:54:08
合計ジャッジ時間 27,242 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 666 ms
69,696 KB
testcase_01 AC 663 ms
69,636 KB
testcase_02 AC 667 ms
69,632 KB
testcase_03 AC 664 ms
69,692 KB
testcase_04 AC 667 ms
69,636 KB
testcase_05 AC 667 ms
69,704 KB
testcase_06 AC 678 ms
69,808 KB
testcase_07 AC 673 ms
69,780 KB
testcase_08 AC 668 ms
69,932 KB
testcase_09 AC 668 ms
69,844 KB
testcase_10 AC 672 ms
69,940 KB
testcase_11 AC 953 ms
70,976 KB
testcase_12 AC 964 ms
70,948 KB
testcase_13 AC 963 ms
70,856 KB
testcase_14 AC 663 ms
69,696 KB
testcase_15 AC 671 ms
69,776 KB
testcase_16 AC 669 ms
69,640 KB
testcase_17 AC 671 ms
69,920 KB
testcase_18 AC 667 ms
69,928 KB
testcase_19 AC 669 ms
69,936 KB
testcase_20 AC 900 ms
71,252 KB
testcase_21 AC 895 ms
71,284 KB
testcase_22 AC 674 ms
69,792 KB
testcase_23 AC 673 ms
69,696 KB
testcase_24 AC 670 ms
69,852 KB
testcase_25 AC 978 ms
70,792 KB
testcase_26 AC 978 ms
70,864 KB
testcase_27 AC 972 ms
70,788 KB
testcase_28 AC 962 ms
70,928 KB
testcase_29 AC 850 ms
70,920 KB
testcase_30 AC 757 ms
70,420 KB
testcase_31 AC 666 ms
69,844 KB
testcase_32 AC 850 ms
71,028 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

mod = 10 ** 6 + 3
denom = 10 ** 40
fac = [1] * mod
inv = [1] * mod

for i in xrange(2, mod):
    fac[i] = i * fac[i - 1] % mod
    inv[i] = (mod - mod / i) * inv[mod % i] % mod

def solve():
    def binom(n, m):
        if n < m: return 0
        if n == m or m == 0: return 1
        nq, nr = divmod(n, mod)
        mq, mr = divmod(m, mod)
        if nr < mr: return 0
        return fac[nr] * inv[fac[mr]] * inv[fac[nr - mr]] * binom(nq, mq) % mod

    counts = map(int, raw_input().split())
    s = raw_input()
    n = len(s)
    lens = []
    for i in xrange(26):
        lens.append({})
    freqs = [0] * 26
    last, cnt = -1, 0
    for c in s:
        i = ord(c) - ord('a')
        if last == i:
            cnt += 1
        else:
            if cnt:
                if cnt in lens[last]:
                    lens[last][cnt] += 1
                else:
                    lens[last][cnt] = 1
            cnt = 1
        freqs[i] += 1
        last = i
    if cnt in lens[last]:
        lens[last][cnt] += 1
    else:
        lens[last][cnt] = 1
    lens = [x.items() for x in lens]
    ans = 1
    for i in xrange(26):
        if counts[i] < freqs[i]:
            return 0
        if freqs[i] == 0 or counts[i] == freqs[i]:
            continue
        if len(lens[i]) == 1 and lens[i][0][1] == 1:
            ans = ans * binom(counts[i], lens[i][0][0]) % mod
        else:
            rest = counts[i] - freqs[i]
            ok = denom + 1
            ng = n * denom + 1
            exact = False
            while ng - ok > 1:
                mid = (ok + ng) >> 1
                total = 0
                for l, c in lens[i]:
                    total += (l * denom) / (mid - denom) * c
                if total >= rest:
                    ok = mid
                    if total == rest:
                        exact = True
                        ng = mid
                else:
                    ng = mid
            for l, c in lens[i]:
                k = (l * denom) / (ng - denom)
                if k:
                    ans = ans * pow(binom(l + k, l) % mod, c, mod) % mod
                    rest -= k * c
            assert rest >= 0
            if not exact:
                for l, c in lens[i]:
                    k1 = (l * denom) / (ok - denom)
                    k2 = (l * denom) / (ng - denom)
                    if k1 > k2:
                        assert k1 == k2 + 1
                        ans = ans * pow((k1 + l) * inv[k1 % mod] % mod, min(rest, c), mod) % mod
                        rest -= min(rest, c)
                        if rest == 0:
                            break
    return ans

print solve()
0