結果
問題 | No.603 hel__world (2) |
ユーザー | zimpha |
提出日時 | 2017-12-03 02:43:42 |
言語 | PyPy2 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,226 bytes |
コンパイル時間 | 2,167 ms |
コンパイル使用メモリ | 77,492 KB |
実行使用メモリ | 139,476 KB |
最終ジャッジ日時 | 2023-08-18 22:21:30 |
合計ジャッジ時間 | 12,429 ms |
ジャッジサーバーID (参考情報) |
judge10 / judge9 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 116 ms
93,064 KB |
testcase_01 | AC | 116 ms
93,028 KB |
testcase_02 | AC | 145 ms
94,736 KB |
testcase_03 | AC | 115 ms
92,932 KB |
testcase_04 | AC | 116 ms
93,116 KB |
testcase_05 | AC | 119 ms
93,988 KB |
testcase_06 | AC | 115 ms
93,300 KB |
testcase_07 | AC | 119 ms
94,140 KB |
testcase_08 | AC | 116 ms
92,996 KB |
testcase_09 | AC | 120 ms
93,084 KB |
testcase_10 | AC | 119 ms
92,892 KB |
testcase_11 | WA | - |
testcase_12 | WA | - |
testcase_13 | WA | - |
testcase_14 | AC | 116 ms
92,916 KB |
testcase_15 | AC | 116 ms
93,088 KB |
testcase_16 | AC | 117 ms
93,140 KB |
testcase_17 | AC | 120 ms
94,420 KB |
testcase_18 | AC | 119 ms
94,220 KB |
testcase_19 | AC | 119 ms
94,012 KB |
testcase_20 | AC | 156 ms
96,792 KB |
testcase_21 | AC | 143 ms
96,916 KB |
testcase_22 | AC | 124 ms
94,852 KB |
testcase_23 | AC | 130 ms
94,856 KB |
testcase_24 | AC | 131 ms
95,020 KB |
testcase_25 | TLE | - |
testcase_26 | -- | - |
testcase_27 | -- | - |
testcase_28 | -- | - |
testcase_29 | -- | - |
testcase_30 | -- | - |
testcase_31 | -- | - |
testcase_32 | -- | - |
ソースコード
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)] freqs = [0] * 26 last = ' ' for c in s: i = ord(c) - ord('a') if last == c: lens[i][-1] += 1 else: lens[i].append(1) freqs[i] += 1 last = c 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: ans = ans * binom(counts[i], lens[i][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 in lens[i]: total += (l * denom) / (mid - denom) if total >= rest: ok = mid if total == rest: exact = True ng = mid else: ng = mid for l in lens[i]: k = (l * denom) / (ng - denom) if k: ans = ans * binom(l + k, l) % mod rest -= k assert rest >= 0 if not exact: for l in lens[i]: k1 = (l * denom) / (ok - denom) k2 = (l * denom) / (ng - denom) if k1 > k2: assert k1 == k2 + 1 ans = ans * (k1 + l) % mod * inv[k1 % mod] % mod rest -= 1 if rest == 0: break return ans print solve()