結果
問題 | No.603 hel__world (2) |
ユーザー | chocorusk |
提出日時 | 2020-02-23 17:43:20 |
言語 | Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0) |
結果 |
AC
|
実行時間 | 1,377 ms / 3,000 ms |
コード長 | 1,509 bytes |
コンパイル時間 | 97 ms |
コンパイル使用メモリ | 12,928 KB |
実行使用メモリ | 62,696 KB |
最終ジャッジ日時 | 2024-04-18 12:11:44 |
合計ジャッジ時間 | 26,955 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 496 ms
50,832 KB |
testcase_01 | AC | 486 ms
50,772 KB |
testcase_02 | AC | 505 ms
50,788 KB |
testcase_03 | AC | 535 ms
50,784 KB |
testcase_04 | AC | 502 ms
50,756 KB |
testcase_05 | AC | 503 ms
50,912 KB |
testcase_06 | AC | 482 ms
50,932 KB |
testcase_07 | AC | 498 ms
50,724 KB |
testcase_08 | AC | 478 ms
50,820 KB |
testcase_09 | AC | 481 ms
50,860 KB |
testcase_10 | AC | 519 ms
50,816 KB |
testcase_11 | AC | 1,224 ms
62,440 KB |
testcase_12 | AC | 1,169 ms
62,056 KB |
testcase_13 | AC | 1,241 ms
62,292 KB |
testcase_14 | AC | 504 ms
50,760 KB |
testcase_15 | AC | 487 ms
50,784 KB |
testcase_16 | AC | 496 ms
50,768 KB |
testcase_17 | AC | 499 ms
50,816 KB |
testcase_18 | AC | 488 ms
50,816 KB |
testcase_19 | AC | 490 ms
50,712 KB |
testcase_20 | AC | 1,107 ms
52,728 KB |
testcase_21 | AC | 1,058 ms
52,728 KB |
testcase_22 | AC | 487 ms
50,928 KB |
testcase_23 | AC | 487 ms
50,756 KB |
testcase_24 | AC | 500 ms
50,768 KB |
testcase_25 | AC | 1,377 ms
62,180 KB |
testcase_26 | AC | 1,354 ms
62,696 KB |
testcase_27 | AC | 1,352 ms
62,312 KB |
testcase_28 | AC | 1,307 ms
60,516 KB |
testcase_29 | AC | 1,016 ms
52,728 KB |
testcase_30 | AC | 883 ms
51,732 KB |
testcase_31 | AC | 504 ms
50,816 KB |
testcase_32 | AC | 1,153 ms
52,860 KB |
ソースコード
from decimal import * from fractions import Fraction getcontext().prec=55 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(120): 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)