Problem p03776 (python)

Fixed submission:
# nの逆元のリスト
def inv_mod(n:int, mod:int) -> list:
    inv = [-1,1]
    for i in range(2,n+1):
        inv.append(mod - ((mod//i)*inv[mod%i]) % mod)
    return inv
       
# nの階乗のリスト
def fact(n:int, mod:int) -> list:
    fac = [1,1]
    res = 1
    for i in range(2,n+1):
        res = res*i%mod
        fac.append(res)
    return fac

# nの階乗の逆元のリスト
def fact_inv(n:int, inv:list, mod:int) -> list:
    facInv = [1,1]
    for i in range(2,n+1):
        facInv.append(facInv[i-1]*inv[i] % mod)
    return facInv
        
# 二項係数
def nCr(n:int, r:int, mod:int, fac:list, facInv:list) -> int:
    if not (0<=r and r<=n):
        return 0
    
    return ((fac[n]*facInv[r]) % mod) * facInv[n-r] % mod

N,A,B = map(int, input().split())
V = list(map(int, input().split()))

# 二項係数の準備
MOD = 9007199254740997
inv = inv_mod(N,MOD)
fac = fact(N,MOD)
facInv = fact_inv(N,inv,MOD)

V.sort(reverse=True)

max_avg = sum(V[:A])/A
print(max_avg)

ans = 0
if V[0] == V[A-1]:
    v = V.count(V[A-1])
    u = min(v,B)
    for i in range(A,u+1):
        ans += nCr(v,i,MOD,fac,facInv)

else:
    v_all = V.count(V[A-1])
    v_ch = V[:A].count(V[A-1])
    ans = nCr(v_all,v_ch,MOD,fac,facInv)

print(ans)

Buggy submission (verdict: Runtime Error):
import sys
stdin = sys.stdin

def li(): return [int(x) for x in stdin.readline().split()]
def li_(): return [int(x)-1 for x in stdin.readline().split()]
def lf(): return [float(x) for x in stdin.readline().split()]
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(ns())
def nf(): return float(ns())

# nの逆元のリスト
def inv_mod(n:int, mod:int) -> list:
    inv = [0,1]
    for i in range(2,n+1):
        inv.append(mod - ((mod//i)*inv[mod%i]) % mod)
    return inv
       
# nの階乗のリスト
def fact(n:int, mod:int) -> list:
    fac = [1,1]
    res = 1
    for i in range(2,n+1):
        res = res*i%mod
        fac.append(res)
    return fac

# nの階乗の逆元のリスト
def fact_inv(n:int, inv:list, mod:int) -> list:
    facInv = [1,1]
    for i in range(2,n+1):
        facInv.append(facInv[i-1]*inv[i] % mod)
    return facInv
        
# 二項係数
def nCr(n:int, r:int, mod:int, fac:list, facInv:list) -> int:
    if not (0<=r and r<=n):
        return 0
    
    return ((fac[n]*facInv[r]) % mod) * facInv[n-r] % mod

from itertools import accumulate
from collections import Counter

n,a,b = li()
v = li()

v.sort(reverse=True)
v_cum = list(accumulate(v))

ans_cand = []

# 貪欲に最大値を選ぶ
for i in range(a,b+1):
    ans_cand.append(v_cum[i-1] / i)
    
ans = max(ans_cand)
opt_is = []

while ans in ans_cand:
    opt_is.append(a + ans_cand.index(ans))
    ans_cand[ans_cand.index(int(ans))] = 0
    

cnt_v = Counter(v)

# 貪欲最大が何通りできるか考える
MOD = 46116646144580591
inv = inv_mod(n, MOD)
fac = fact(n, MOD)
facInv = fact_inv(n,inv, MOD)

pat = 0

for opt_i in opt_is:
    opt_set = v[:opt_i]
    cnt_opt = Counter(opt_set)
    
    temp = 1
    
    for key_op, val_op in cnt_opt.items():
        temp *= nCr(cnt_v[key_op], int(val_op), MOD, fac, facInv)
        
    pat += temp
        
print(ans)
print(pat)

Buggy submission (verdict: Runtime Error):
import sys
stdin = sys.stdin

def li(): return [int(x) for x in stdin.readline().split()]
def li_(): return [int(x)-1 for x in stdin.readline().split()]
def lf(): return [float(x) for x in stdin.readline().split()]
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(ns())
def nf(): return float(ns())

# nの逆元のリスト
def inv_mod(n:int, mod:int) -> list:
    inv = [0,1]
    for i in range(2,n+1):
        inv.append(mod - ((mod//i)*inv[mod%i]) % mod)
    return inv
       
# nの階乗のリスト
def fact(n:int, mod:int) -> list:
    fac = [1,1]
    res = 1
    for i in range(2,n+1):
        res = res*i%mod
        fac.append(res)
    return fac

# nの階乗の逆元のリスト
def fact_inv(n:int, inv:list, mod:int) -> list:
    facInv = [1,1]
    for i in range(2,n+1):
        facInv.append(facInv[i-1]*inv[i] % mod)
    return facInv
        
# 二項係数
def nCr(n:int, r:int, mod:int, fac:list, facInv:list) -> int:
    if not (0<=r and r<=n):
        return 0
    
    return ((fac[n]*facInv[r]) % mod) * facInv[n-r] % mod

from itertools import accumulate
from collections import Counter

n,a,b = li()
v = li()

v.sort(reverse=True)
v_cum = list(accumulate(v))

ans_cand = []

# 貪欲に最大値を選ぶ
for i in range(a,b+1):
    ans_cand.append(v_cum[i-1] / i)
    
ans = max(ans_cand)
opt_is = []

while ans in ans_cand:
    opt_is.append(a + ans_cand.index(ans))
    ans_cand[ans_cand.index(int(ans))] = 0
    

cnt_v = Counter(v)

# 貪欲最大が何通りできるか考える
MOD = 10**18+1
inv = inv_mod(n, MOD)
fac = fact(n, MOD)
facInv = fact_inv(n,inv, MOD)

pat = 0

for opt_i in opt_is:
    opt_set = v[:opt_i]
    cnt_opt = Counter(opt_set)
    
    temp = 1
    
    for key_op, val_op in cnt_opt.items():
        temp *= nCr(cnt_v[key_op], int(val_op), MOD, fac, facInv)
        
    pat += temp
        
print(ans)
print(pat)