結果

問題 No.1039 Project Euler でやれ
ユーザー lam6er
提出日時 2025-03-26 15:51:42
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,707 bytes
コンパイル時間 294 ms
コンパイル使用メモリ 82,780 KB
実行使用メモリ 78,788 KB
最終ジャッジ日時 2025-03-26 15:52:33
合計ジャッジ時間 2,052 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 13 WA * 5
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from itertools import product

MOD = 10**9 + 7

def main():
    M = int(sys.stdin.readline())
    if M == 1:
        print(1)
        return
    
    # Precompute factorial
    max_fact = M
    fact = [1] * (max_fact + 1)
    for i in range(1, max_fact + 1):
        fact[i] = fact[i-1] * i % MOD
    
    # Prime factorization
    def prime_factors(m):
        factors = {}
        i = 2
        while i * i <= m:
            while m % i == 0:
                factors[i] = factors.get(i, 0) + 1
                m = m // i
            i += 1
        if m > 1:
            factors[m] = 1
        return factors
    
    factors = prime_factors(M)
    if not factors:
        print(0)
        return
    
    primes = list(factors.keys())
    
    # Function to generate partitions of an integer n in decreasing order
    def generate_partitions(n):
        partitions = []
        def dfs(remaining, path, start):
            if remaining == 0:
                partitions.append(path.copy())
                return
            if start == 0:
                return
            next_start = min(start, remaining)
            for i in range(next_start, 0, -1):
                path.append(i)
                dfs(remaining - i, path, min(i, remaining - i))
                path.pop()
        dfs(n, [], n)
        return partitions
    
    # Group the partition into (value, count)
    def group_partition(partition):
        if not partition:
            return []
        groups = []
        current_val = partition[0]
        count = 1
        for val in partition[1:]:
            if val == current_val:
                count += 1
            else:
                groups.append((current_val, count))
                current_val = val
                count = 1
        groups.append((current_val, count))
        return groups
    
    # Compute the p-component of the automorphism group size for a given partition of exponent e_p
    def compute_p_aut(p, groups):
        aut = 1
        # Compute GL part for each group
        for (e, d) in groups:
            # Calculate |GL(d, p)|
            gl = 1
            for k in range(d):
                term = (pow(p, d, MOD) - pow(p, k, MOD)) % MOD
                gl = gl * term % MOD
            # Multiply by p^{(e-1)*d^2}
            exponent = (e - 1) * d * d
            gl = gl * pow(p, exponent, MOD) % MOD
            aut = aut * gl % MOD
        # Compute homomorphism part between groups i < j
        hom_exponent = 0
        for i in range(len(groups)):
            e_i, d_i = groups[i]
            for j in range(i + 1, len(groups)):
                e_j, d_j = groups[j]
                hom_exponent += d_i * d_j * e_j
        aut = aut * pow(p, hom_exponent, MOD) % MOD
        return aut
    
    # Generate all possible partitions for each prime factor
    part_lists = {}
    for p in primes:
        e_p = factors[p]
        part = generate_partitions(e_p)
        part_lists[p] = part
    
    # Generate all combinations of partitions (Cartesian product)
    components = []
    for p in primes:
        components.append(part_lists[p])
    class_combinations = product(*components)
    
    answer = 0
    for comb in class_combinations:
        aut_size = 1
        for i in range(len(primes)):
            p = primes[i]
            partition = comb[i]
            groups = group_partition(partition)
            p_aut = compute_p_aut(p, groups)
            aut_size = aut_size * p_aut % MOD
        # Compute term: M! / aut_size mod MOD
        inv_aut = pow(aut_size, MOD-2, MOD)
        term = fact[M] * inv_aut % MOD
        answer = (answer + term) % MOD
    
    print(answer)

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