結果
問題 |
No.1419 Power Moves
|
ユーザー |
![]() |
提出日時 | 2025-03-31 17:47:42 |
言語 | PyPy3 (7.3.15) |
結果 |
MLE
|
実行時間 | - |
コード長 | 996 bytes |
コンパイル時間 | 345 ms |
コンパイル使用メモリ | 82,152 KB |
実行使用メモリ | 858,280 KB |
最終ジャッジ日時 | 2025-03-31 17:48:52 |
合計ジャッジ時間 | 5,164 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 6 MLE * 1 -- * 24 |
ソースコード
MOD = 10**9 + 7 def main(): import sys sys.setrecursionlimit(1 << 25) N, K = map(int, sys.stdin.readline().split()) # Compute s_j = 2^j mod N for j in 0..K-1 s = [] current = 1 for j in range(K): s_j = current % N s.append(s_j) current = (current * 2) % (2 * N) # To avoid overflow, mod 2*N # Dynamic programming approach dp = [0] * N dp[0] = 1 # Start at position 0 for j in range(K): new_dp = [0] * N s_j = s[j] for r in range(N): p = dp[r] * pow(2, MOD-2, MOD) % MOD new_r1 = (r + s_j) % N new_r2 = (r - s_j) % N new_dp[new_r1] = (new_dp[new_r1] + p) % MOD new_dp[new_r2] = (new_dp[new_r2] + p) % MOD dp = new_dp inv = pow(1, MOD-2, MOD) # since denominator is 1, because we already multiplied by 1/2 each time for r in range(N): print(dp[r] * inv % MOD) if __name__ == '__main__': main()