結果

問題 No.125 悪の花弁
コンテスト
ユーザー lam6er
提出日時 2025-03-20 20:52:45
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 234 ms / 5,000 ms
コード長 1,944 bytes
コンパイル時間 359 ms
コンパイル使用メモリ 82,284 KB
実行使用メモリ 118,948 KB
最終ジャッジ日時 2025-03-20 20:53:01
合計ジャッジ時間 2,103 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 6
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
import math
from math import gcd
from functools import reduce
from collections import defaultdict

MOD = 10**9 + 7

# Precompute factorial, inverse factorial, and phi up to 1e6
MAX = 10**6

# Factorial and inverse factorial
fact = [1] * (MAX + 1)
for i in range(1, MAX + 1):
    fact[i] = fact[i-1] * i % MOD

inv_fact = [1] * (MAX + 1)
inv_fact[MAX] = pow(fact[MAX], MOD-2, MOD)
for i in range(MAX-1, -1, -1):
    inv_fact[i] = inv_fact[i+1] * (i+1) % MOD

# Euler's totient function (phi)
phi = list(range(MAX + 1))
for i in range(2, MAX + 1):
    if phi[i] == i:  # i is prime
        for j in range(i, MAX + 1, i):
            phi[j] -= phi[j] // i

def compute_gcd(arr):
    return reduce(math.gcd, arr)

def get_divisors(n):
    divisors = set()
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.add(i)
            divisors.add(n//i)
    return sorted(divisors)

def main():
    input = sys.stdin.read().split()
    K = int(input[0])
    C = list(map(int, input[1:1+K]))
    N = sum(C)
    if N == 0:
        print(0)
        return
    
    G = compute_gcd(C)
    divisors = get_divisors(N)
    
    total = 0
    valid_g = []
    
    for g in divisors:
        d_prime = N // g
        if G % d_prime != 0:
            continue
        valid_g.append(g)
    
    for g in valid_g:
        d_prime = N // g
        s_list = [c // d_prime for c in C]
        
        s_counts = defaultdict(int)
        for s in s_list:
            s_counts[s] += 1
        
        product_inv = 1
        for s, cnt in s_counts.items():
            inv = pow(inv_fact[s], cnt, MOD)
            product_inv = product_inv * inv % MOD
        
        comb = fact[g] * product_inv % MOD
        phi_val = phi[d_prime]  # phi(N/g) = phi(d_prime)
        total = (total + comb * phi_val) % MOD
    
    inv_N = pow(N, MOD-2, MOD)
    ans = total * inv_N % MOD
    print(ans)

if __name__ == "__main__":
    main()
0