結果

問題 No.125 悪の花弁
コンテスト
ユーザー rpy3cpp
提出日時 2015-11-16 01:08:31
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
RE  
(最新)
AC  
(最初)
実行時間 -
コード長 2,392 bytes
コンパイル時間 218 ms
コンパイル使用メモリ 12,928 KB
実行使用メモリ 91,104 KB
最終ジャッジ日時 2024-09-13 15:22:36
合計ジャッジ時間 3,865 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other RE * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

import fractions  # fractions.gcd を使う。なお、Python 3.5 から、gcd は、math パッケージに移行している。
import functools


def inv(n, mod):
    ''' mod を法とした n の逆元 ret を返す
    (n * ret) % mod = 1 となる 
    '''
    b = bin(mod-2)[2:][-1::-1]
    ret = 1
    tmp = n % mod
    if b[0] == '1':
        ret = n % mod
    for bi in b[1:]:
        tmp *= tmp
        tmp %= mod
        if bi == '1':
            ret *= tmp
            ret %= mod
    return ret


def init_factorials(N, mod):
    f = 1
    fac = [1] * (N + 1)
    for i in range(1, N + 1):
        f *= i
        f %= mod
        fac[i] = f
    return fac


def init_invfac(N, mod, fac):
    ret = inv(fac[N], mod)
    invfac = [1] * (N + 1)
    invfac[N] = ret
    for i in range(N-1, 0, -1):
        ret *= i + 1
        ret %= mod
        invfac[i] = ret
    return invfac


def read_data():
    K = int(input())
    Cs = list(map(int, input().split()))
    return K, Cs


def solve(K, Cs):
    N = sum(Cs)
    mod = 10**9 + 7
    fac = init_factorials(N, mod)
    invfac = init_invfac(N, mod, fac)
    div = functools.reduce(fractions.gcd, Cs)
    divs = find_divs(div)
    ans = calc(N, divs, Cs, fac, invfac, mod)
    return ans


def find_divs(div):
    ''' div の約数(div, 1 を含む)の降順のリストを返す
    '''
    divs_small = []
    divs_large = []
    t = int(div ** 0.5)
    for c in range(1, t + 1):
        if div % c:
            continue
        divs_small.append(c)
        divs_large.append(div // c)
    if t * t == div:
        del divs_small[-1]
    divs_large.extend(divs_small[::-1])
    return divs_large


def calc(N, divs, Cs, fac, invfac, mod):
    gs = calc_gs(N, divs, Cs, fac, invfac, mod)
    hs = calc_hs(divs, gs, mod)
    return sum(h * inv(N//d, mod) for h, d in zip(hs, divs)) % mod

def calc_gs(N, divs, Cs, fac, invfac, mod):
    gs = []
    for d in divs:
        g = fac[N//d]
        for c in Cs:
            g *= invfac[c//d]
            g %= mod
        gs.append(g)
    return gs

def calc_hs(divs, gs, mod):
    hs = []
    for di, gi in zip(divs, gs):
        h = gi
        for dj, hj in zip(divs, hs):
            if di == dj:
                break
            if dj % di:
                continue
            h -= hj
            h %= mod
        hs.append(h)
    return hs


K, Cs = read_data()
print(solve(K, Cs))
0