結果
問題 |
No.1419 Power Moves
|
ユーザー |
![]() |
提出日時 | 2025-04-15 21:09:09 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,265 bytes |
コンパイル時間 | 338 ms |
コンパイル使用メモリ | 82,212 KB |
実行使用メモリ | 77,616 KB |
最終ジャッジ日時 | 2025-04-15 21:14:44 |
合計ジャッジ時間 | 4,139 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 22 WA * 9 |
ソースコード
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()