結果

問題 No.2146 2 Pows
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 18:49:25
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,533 bytes
コンパイル時間 265 ms
コンパイル使用メモリ 81,928 KB
実行使用メモリ 469,840 KB
最終ジャッジ日時 2025-06-12 18:49:32
合計ジャッジ時間 5,868 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 3 TLE * 1 -- * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

import heapq

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    N = int(data[0])
    A = int(data[1])
    B = int(data[2])
    C = int(data[3])
    
    max_a = 60  # Precompute up to 2^60 mod N
    
    # Precompute 2^a mod N for a up to max_a
    pow_mod = []
    for a in range(max_a + 1):
        pow_mod.append(pow(2, a, N))
    
    # Initialize distance array: dist[residue][max_a] = minimal cost
    INF = float('inf')
    dist = [ [INF] * (max_a + 1) for _ in range(N) ]
    heap = []
    
    for a in range(max_a + 1):
        r = pow_mod[a]
        cost = A + B + C * a
        if cost < dist[r][a]:
            dist[r][a] = cost
            heapq.heappush(heap, (cost, r, a))
    
    while heap:
        current_cost, current_r, current_m = heapq.heappop(heap)
        if current_cost > dist[current_r][current_m]:
            continue
        for a in range(current_m, max_a + 1):
            r_a = pow_mod[a]
            new_r = (current_r + r_a) % N
            added_B = B if a > current_m else 0
            new_cost = current_cost + A + added_B + C * (a - current_m)
            if new_cost < dist[new_r][a]:
                dist[new_r][a] = new_cost
                heapq.heappush(heap, (new_cost, new_r, a))
    
    # Now compute the answer for each k
    for k in range(N):
        min_cost = INF
        for a in range(max_a + 1):
            if dist[k][a] < min_cost:
                min_cost = dist[k][a]
        print(min_cost)
    
if __name__ == '__main__':
    main()
0