結果

問題 No.1419 Power Moves
ユーザー lam6er
提出日時 2025-04-16 15:29:42
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,010 bytes
コンパイル時間 463 ms
コンパイル使用メモリ 82,112 KB
実行使用メモリ 82,296 KB
最終ジャッジ日時 2025-04-16 15:32:49
合計ジャッジ時間 6,205 ms
ジャッジサーバーID
(参考情報)
judge4 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 22 WA * 9
権限があれば一括ダウンロードができます

ソースコード

diff #

import sys
import math

MOD = 10**9 + 7

def modinv(a, mod):
    return pow(a, mod - 2, mod)

def main():
    input = sys.stdin.read().split()
    N = int(input[0])
    K = int(input[1])
    
    pow2K_modN = pow(2, K, N)
    pow2K_modMOD = pow(2, K, MOD)
    inv2K_modMOD = modinv(pow2K_modMOD, MOD)
    
    d = math.gcd(2, N)
    
    results = []
    for n in range(N):
        target = (n + pow2K_modN - 1) % N
        if target % d != 0:
            results.append(0)
            continue
        
        m = N // d
        new_target = (target // d) % m
        
        a = (2 // d) % m
        inv_a = modinv(a, m)
        c = (new_target * inv_a) % m
        
        r = pow(2, K, m)
        t = 1 if r >= c + 1 else 0
        
        numerator = (m * t - r) % MOD
        term = (1 + numerator * inv2K_modMOD) % MOD
        inv_m = modinv(m, MOD)
        ans = (term * inv_m) % MOD
        results.append(ans)
    
    for res in results:
        print(res)

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