結果

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

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 78 ms
85,408 KB
testcase_01 AC 101 ms
108,832 KB
testcase_02 AC 99 ms
108,892 KB
testcase_03 AC 107 ms
109,056 KB
testcase_04 AC 73 ms
83,340 KB
testcase_05 AC 73 ms
83,340 KB
権限があれば一括ダウンロードができます

ソースコード

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]]

ans = 0
for k,v in d.items():
    ans += v*inv[k]%MOD
print(ans%MOD)
0