結果

問題 No.1419 Power Moves
ユーザー lam6er
提出日時 2025-04-15 20:59:25
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 401 ms / 2,000 ms
コード長 1,012 bytes
コンパイル時間 306 ms
コンパイル使用メモリ 81,660 KB
実行使用メモリ 77,116 KB
最終ジャッジ日時 2025-04-15 21:01:56
合計ジャッジ時間 8,040 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 31
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import math

MOD = 10**9 + 7

def main():
    N, K = map(int, sys.stdin.readline().split())
    inv_2K = pow(2, K, MOD)
    inv_2K = pow(inv_2K, MOD-2, MOD)
    pow_2K_mod_N = pow(2, K, N)
    
    for m in range(N):
        D = (pow_2K_mod_N - 1 - m) % N
        g = math.gcd(2, N)
        if D % g != 0:
            print(0)
            continue
        
        M = N // g
        D_prime = D // g
        a_over_g = 2 // g
        
        try:
            inv_2_over_g = pow(a_over_g, -1, M)
        except ValueError:
            print(0)
            continue
        
        T0 = (D_prime * inv_2_over_g) % M
        
        b = pow(2, K, M)
        pow_2K_mod_MMOD = pow(2, K, M * MOD)
        inv_M = pow(M, MOD-2, MOD)
        a = ((pow_2K_mod_MMOD - b) * inv_M) % MOD
        
        if b >= T0 + 1:
            count = (a + 1) % MOD
        else:
            count = a % MOD
        
        res = (count * inv_2K) % MOD
        print(res)
        
if __name__ == "__main__":
    main()
0