結果

問題 No.125 悪の花弁
ユーザー convexineqconvexineq
提出日時 2020-12-18 21:14:23
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,107 bytes
コンパイル時間 1,613 ms
コンパイル使用メモリ 81,376 KB
実行使用メモリ 110,880 KB
最終ジャッジ日時 2023-10-21 08:22:16
合計ジャッジ時間 1,384 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge9
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

SIZE=10**6+10; MOD=10**9+7 #998244353 #ここを変更する

inv = [0]*SIZE  # inv[j] = j^{-1} mod MOD
fac = [0]*SIZE  # fac[j] = j! mod MOD
finv = [0]*SIZE # finv[j] = (j!)^{-1} mod MOD
fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
for i in range(2,SIZE):
    fac[i] = fac[i-1]*i%MOD
finv[-1] = pow(fac[-1],MOD-2,MOD)
for i in range(SIZE-1,0,-1):
    finv[i-1] = finv[i]*i%MOD
    inv[i] = finv[i]*fac[i-1]%MOD

def divisor_list(N): #約数のリスト
    if N == 1: return [1]
    res = []
    for i in range(1,N):
        if i*i >= N: break
        if N%i == 0:
            res.append(i)
            res.append(N//i)
    if i*i == N: res.append(i)
    return sorted(res)

_ = int(input())
*a, = map(int,input().split())
n = sum(a)
div = divisor_list(n)

d = {x:0 for x in div}
for p in div:
    r = fac[n//p]
    for ai in a:
        if ai%p: break
        r = r*finv[ai//p]%MOD
    else:
        d[n//p] = r

L = len(div)
for i in range(L):
    for j in range(i):
        if div[i]%div[j]==0:
            d[div[i]] -= d[div[j]]
print(d)
ans = 0
for k,v in d.items():
    ans += v*inv[k]%MOD
print(ans%MOD)
0