結果

問題 No.3123 Inversion
ユーザー keigo kuwata
提出日時 2025-04-23 08:56:49
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
TLE  
実行時間 -
コード長 1,342 bytes
コンパイル時間 215 ms
コンパイル使用メモリ 12,544 KB
実行使用メモリ 52,520 KB
最終ジャッジ日時 2025-04-23 08:57:15
合計ジャッジ時間 25,561 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 1
other TLE * 1 -- * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

def solve(n, mod):
    # 特別なケース
    if n == 1:
        return 1
    
    # 高速累乗計算（mod付き）
    def pow_mod(x, y, mod):
        result = 1
        x = x % mod
        while y > 0:
            if y % 2 == 1:
                result = (result * x) % mod
            y = y // 2
            x = (x * x) % mod
        return result
    
    # 巡回置換の数を計算
    def count_cycles(n):
        cycles = [0] * (n + 1)
        for i in range(1, n + 1):
            for j in range(i, n + 1, i):
                cycles[j] = (cycles[j] + pow_mod(i, mod - 2, mod)) % mod
        return cycles
    
    # 順列の数を計算
    fact = [1]
    for i in range(1, n + 1):
        fact.append((fact[-1] * i) % mod)
    
    # 軌道の数と大きさを計算
    cycles = count_cycles(n)
    
    # 結果を計算
    result = 0
    for i in range(1, n + 1):
        orbit_size = (n // i) * 2  # 各軌道のサイズ
        orbit_count = (fact[n] * cycles[i]) % mod  # 軌道の数
        result = (result + orbit_count * orbit_size) % mod
    
    return result

def main():
    t, m = map(int, input().split())
    results = []
    
    for _ in range(t):
        n = int(input())
        results.append(solve(n, m))
    
    for result in results:
        print(result)

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