結果
問題 |
No.1419 Power Moves
|
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
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()