結果

問題 No.125 悪の花弁
コンテスト
ユーザー navel_tos
提出日時 2025-01-17 02:32:53
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 149 ms / 5,000 ms
コード長 2,248 bytes
コンパイル時間 2,896 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 113,432 KB
最終ジャッジ日時 2025-01-17 02:32:58
合計ジャッジ時間 4,561 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

#yukicoder125 悪の花弁

#愚直解をがんばって書く
def brute(K, C):
    from itertools import permutations
    B = []
    for i, Ci in enumerate(C):
        B.extend( [i] * Ci )
    n = len(B)
    ans = set()
    for P in permutations(B):
        for i in range(n):
            Q = tuple( P[i:] + P[:i] )
            if Q in ans:
                break
        else:
            ans.add(P)
    return len( ans )


def solve(K, C):
    #花弁の枚数をN, gcd(C)をgとする
    #gの約数個を単位に並べる  これをシフトしよう
    #下処理として約数列挙まではやっておく
    N = sum(C)
    MOD = 10 ** 9 + 7  #998244353にしていました すいません
    fact = [ v := 1 ] + [ v := v * i % MOD for i in range(1, N + 1) ]
    finv = [ v := pow(v, -1, MOD) ] + [ v := v * i % MOD for i in range(N, 0, -1) ]
    finv.reverse()
    
    gcd = lambda x, y: gcd(y, x % y) if y else abs(x)
    g = 0
    for Ci in C:
        g = gcd(g, Ci)
    D = []
    for i in range(1, g + 1):
        if i ** 2 > g:
            break
        if g % i == 0:
            D.append(i)
            if i ** 2 != g:
                D.append(g // i)
    D.sort()  #周期列挙

    #一旦円環のことは忘れる
    #F[i]: 同色g // i枚を1セットとして一列に並べる場合の数
    #      ただし、F[i]の候補が複数ある場合は最大のg // i → 最小のi でカウントする
    #G[i]: 同色g // i枚を1セットとして一列に並べる場合の数
    F = [0] * (g + 1)
    G = [0] * (g + 1)
    for i in D:
        pair = g // i
        G[i] = fact[ N // pair ]
        for Ci in C:
            G[i] *= finv[ Ci // pair ]
            G[i] %= MOD

    #約数包除でF[i]を求める  包除というか力業だけど
    for i in D:
        F[i] = G[i]
        for j in D:
            if j < i and i % j == 0:
                F[i] -= F[j]
                F[i] %= MOD

    #答えを計算　g // i枚1セットなので総セット数は N // ( g // i) セット
    ans = 0
    for i in D:
        cnt = N // ( g // i )
        ans += F[i] * pow(cnt, -1, MOD)
        ans %= MOD
    return ans


#実行
print( solve( K := int(input()), C := list(map(int, input().split())) ) )
0