結果

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

ソースコード

diff # 

import sys
import math

MOD = 10**9 + 7

def main():
    N, K = map(int, sys.stdin.readline().split())
    
    d = math.gcd(2, N)
    pow_2k_modN = pow(2, K, N)
    rem = (pow_2k_modN - 1) % N
    
    # Compute pow_2k_modNM = 2^K mod (N * MOD)
    mod_nm = N * MOD
    pow_2k_modNM = pow(2, K, mod_nm)
    val = (pow_2k_modNM - 1 - rem) % mod_nm
    inv_N = pow(N, MOD-2, MOD)
    q_mod = (val * inv_N) % MOD
    
    # Compute inv_2k = 1/(2^K) mod MOD
    pow_2k = pow(2, K, MOD)
    inv_2k = pow(pow_2k, MOD-2, MOD)
    
    # Precompute inv_2d for d=1 and d=2
    if d == 1:
        M = N
        inv_2d = pow(2, M-2, M)
    else:
        M = N // 2
        inv_2d = 1
    
    for n in range(N):
        C = (n + pow_2k_modN - 1) % N
        if C % d != 0:
            print(0)
            continue
        
        C_div_d = C // d
        x = (C_div_d * inv_2d) % M
        residues = [(x + k * M) % N for k in range(d)]
        
        sum_counts = 0
        for r in residues:
            if rem >= r:
                sum_counts = (sum_counts + q_mod + 1) % MOD
            else:
                sum_counts = (sum_counts + q_mod) % MOD
        
        prob = (sum_counts * inv_2k) % MOD
        print(prob)
        
if __name__ == "__main__":
    main()
0