結果

問題 No.125 悪の花弁
ユーザー rpy3cpprpy3cpp
提出日時 2015-11-15 15:38:44
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
WA  
実行時間 -
コード長 1,850 bytes
コンパイル時間 323 ms
コンパイル使用メモリ 10,928 KB
実行使用メモリ 88,688 KB
最終ジャッジ日時 2023-10-11 16:22:58
合計ジャッジ時間 3,573 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge14
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 AC 280 ms
66,424 KB
testcase_02 AC 369 ms
88,444 KB
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

import 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(math.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):
    g = 0
    ans = 0
    for d in divs:
        h = fac[N//d]
        for c in Cs:
            h *= invfac[c//d]
            h %= mod
        ans += ((h - g) % mod) * inv(N//d, mod)
        ans %= mod
        g = h
    return ans

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