結果
問題 | No.603 hel__world (2) |
ユーザー | chocorusk |
提出日時 | 2020-02-23 17:29:17 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,763 ms / 3,000 ms |
コード長 | 1,509 bytes |
コンパイル時間 | 208 ms |
コンパイル使用メモリ | 82,560 KB |
実行使用メモリ | 140,720 KB |
最終ジャッジ日時 | 2024-04-18 11:50:03 |
合計ジャッジ時間 | 13,559 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 189 ms
90,924 KB |
testcase_01 | AC | 181 ms
90,392 KB |
testcase_02 | AC | 178 ms
90,692 KB |
testcase_03 | AC | 218 ms
90,880 KB |
testcase_04 | AC | 228 ms
91,136 KB |
testcase_05 | AC | 213 ms
90,512 KB |
testcase_06 | AC | 131 ms
90,152 KB |
testcase_07 | AC | 287 ms
91,296 KB |
testcase_08 | AC | 160 ms
90,092 KB |
testcase_09 | AC | 150 ms
90,368 KB |
testcase_10 | AC | 194 ms
90,752 KB |
testcase_11 | AC | 353 ms
140,720 KB |
testcase_12 | AC | 260 ms
139,948 KB |
testcase_13 | AC | 366 ms
139,840 KB |
testcase_14 | AC | 168 ms
90,280 KB |
testcase_15 | AC | 175 ms
90,368 KB |
testcase_16 | AC | 175 ms
90,496 KB |
testcase_17 | AC | 178 ms
90,640 KB |
testcase_18 | AC | 157 ms
90,144 KB |
testcase_19 | AC | 158 ms
90,368 KB |
testcase_20 | AC | 1,763 ms
94,584 KB |
testcase_21 | AC | 1,744 ms
94,868 KB |
testcase_22 | AC | 437 ms
92,892 KB |
testcase_23 | AC | 438 ms
92,960 KB |
testcase_24 | AC | 467 ms
94,080 KB |
testcase_25 | AC | 646 ms
140,212 KB |
testcase_26 | AC | 759 ms
140,208 KB |
testcase_27 | AC | 730 ms
140,356 KB |
testcase_28 | AC | 251 ms
134,472 KB |
testcase_29 | AC | 208 ms
92,160 KB |
testcase_30 | AC | 189 ms
91,008 KB |
testcase_31 | AC | 156 ms
90,368 KB |
testcase_32 | AC | 190 ms
91,904 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(150): 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)