結果
問題 | No.603 hel__world (2) |
ユーザー | chocorusk |
提出日時 | 2020-02-23 17:30:08 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,509 bytes |
コンパイル時間 | 218 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 140,220 KB |
最終ジャッジ日時 | 2024-04-18 11:52:00 |
合計ジャッジ時間 | 12,223 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 178 ms
90,112 KB |
testcase_01 | AC | 170 ms
90,112 KB |
testcase_02 | AC | 175 ms
90,368 KB |
testcase_03 | AC | 202 ms
90,496 KB |
testcase_04 | AC | 217 ms
90,496 KB |
testcase_05 | AC | 204 ms
90,388 KB |
testcase_06 | AC | 138 ms
89,600 KB |
testcase_07 | AC | 247 ms
91,008 KB |
testcase_08 | AC | 155 ms
90,112 KB |
testcase_09 | AC | 155 ms
89,984 KB |
testcase_10 | AC | 181 ms
90,768 KB |
testcase_11 | AC | 321 ms
140,220 KB |
testcase_12 | AC | 249 ms
139,828 KB |
testcase_13 | AC | 320 ms
139,816 KB |
testcase_14 | AC | 166 ms
90,240 KB |
testcase_15 | WA | - |
testcase_16 | AC | 170 ms
90,240 KB |
testcase_17 | AC | 185 ms
90,240 KB |
testcase_18 | AC | 158 ms
90,240 KB |
testcase_19 | AC | 160 ms
90,240 KB |
testcase_20 | AC | 1,285 ms
94,184 KB |
testcase_21 | AC | 1,282 ms
94,488 KB |
testcase_22 | AC | 395 ms
91,904 KB |
testcase_23 | AC | 362 ms
91,392 KB |
testcase_24 | AC | 429 ms
91,936 KB |
testcase_25 | AC | 607 ms
139,872 KB |
testcase_26 | AC | 613 ms
140,132 KB |
testcase_27 | AC | 628 ms
140,092 KB |
testcase_28 | AC | 249 ms
133,408 KB |
testcase_29 | AC | 187 ms
91,776 KB |
testcase_30 | AC | 185 ms
91,136 KB |
testcase_31 | AC | 152 ms
90,112 KB |
testcase_32 | AC | 197 ms
91,776 KB |
ソースコード
from decimal import * from fractions import Fraction getcontext().prec=60 mod=10**6+3 invs=[0]*mod invs[1]=1 for i in range(2, mod): invs[i]=mod-invs[mod%i]*(mod//i)%mod def solve(x, v): m=len(v) if m==0: return 1 s=sum(v) if x<s: return 0 elif x==s: return 1 v.sort() vs=[] cnt2=1 for i in range(1, m): if v[i]!=v[i-1]: vs.append((v[i-1], cnt2)) cnt2=0 cnt2+=1 vs.append((v[m-1], cnt2)) l=Decimal(1) r=Decimal(max(v)+2) for _ in range(100): mid=(l+r)/Decimal(2) cnt=0 for p in vs: cnt+=p[1]*int(Decimal(p[0])/(mid-Decimal(1))) if cnt<x-s: r=mid else: l=mid ret=1 cnt=0 f=Fraction(10**19, 1) for p in vs: k=int(Decimal(p[0])/(l-Decimal(1))) if k==0: continue f=min(f, Fraction(p[0]+k, k)) cnt+=k*p[1] for i in range(p[0]): ret=ret*pow((k+i+1)*invs[i+1]%mod, p[1], mod)%mod p=f.numerator q=f.denominator ret*=pow(q, cnt-(x-s), mod)*pow(p, mod-1-(cnt-(x-s))%(mod-1), mod) ret%=mod return ret v=[[] for i in range(26)] x=list(map(int, input().split())) t=input() n=len(t) cnt=1 for i in range(1, n): if t[i]!=t[i-1]: v[ord(t[i-1])-ord('a')].append(cnt) cnt=0 cnt+=1 v[ord(t[n-1])-ord('a')].append(cnt) ans=1 for i in range(26): a=solve(x[i], v[i]) #print(a) ans=ans*a%mod print(ans)