結果

問題 No.2146 2 Pows
ユーザー lam6er
提出日時 2025-03-31 17:57:05
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,741 bytes
コンパイル時間 274 ms
コンパイル使用メモリ 82,708 KB
実行使用メモリ 159,508 KB
最終ジャッジ日時 2025-03-31 17:58:33
合計ジャッジ時間 5,974 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 3 TLE * 1 -- * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import heapq

def main():
    N, A, B, C = map(int, sys.stdin.readline().split())
    INF = 1 << 60

    dp = [INF] * N
    dp[0] = 0  # Start with 0, but need to use at least one element

    max_z = 60
    pow2_mod = []
    for z in range(max_z + 1):
        if z == 0:
            pow2_mod.append(1 % N)
        else:
            pow2_mod.append((pow2_mod[-1] * 2) % N)
    
    answer = [INF] * N

    for z in range(max_z + 1):
        m_z = pow2_mod[z]
        new_dp = [INF] * N
        for r in range(N):
            current_cost = dp[r]
            if current_cost == INF:
                continue
            # Try adding t elements of 2^z: t >= 1
            # s = (r + t * m_z) mod N
            for t in range(1, 4):  # Arbitrary upper limit for t (to handle small cases)
                s = (r + t * m_z) % N
                new_cost = current_cost + A * t + B + C * z
                if new_cost < new_dp[s]:
                    new_dp[s] = new_cost
        # Now, merge new_dp into the answer and dp for subsequent steps
        for s in range(N):
            if new_dp[s] < answer[s]:
                answer[s] = new_dp[s]
            if new_dp[s] < dp[s]:
                dp[s] = new_dp[s]
    
    for s in range(N):
        # Also check adding single elements of larger z without using previous states
        # This handles cases where we use only a single exponent
        for z in range(max_z + 1):
            m_z = pow2_mod[z]
            t = 1
            sum_ = (t * m_z) % N
            cost = A * t + B + C * z
            if sum_ == s and cost < answer[s]:
                answer[s] = cost
    
    # Handle the case when the multiset consists of multiple copies of the same exponent
    for s in range(N):
        for z in range(max_z + 1):
            m_z = pow2_mod[z]
            if m_z == 0:
                if s == 0:
                    cost = A * 1 + B + C * z
                    if cost < answer[0]:
                        answer[0] = cost
                continue
            g = gcd(m_z, N)
            required = (s) % g
            if required != 0:
                continue
            # Solve for t*m_z ≡ s mod N, t >=1
            # m_z * t ≡ s mod N
            # find minimal t
            a = m_z
            b = s
            d = gcd(a, N)
            a //= d
            b //= d
            NN = N // d
            try:
                inv_a = pow(a, -1, NN)
            except:
                continue
            t0 = (b * inv_a) % NN
            if t0 == 0:
                t0 = NN
            if t0 < 1:
                t0 += ((-t0) // NN + 1) * NN
            t = t0
            cost = A * t + B + C * z
            if t >= 1:
                sum_mod = (t * m_z) % N
                if sum_mod == s and cost < answer[s]:
                    answer[s] = cost
            # Check t = t0 + k * NN for small k
            for k in range(-2, 3):
                tt = t0 + k * NN
                if tt < 1:
                    continue
                cost = A * tt + B + C * z
                sum_mod = (tt * m_z) % N
                if sum_mod == s and cost < answer[s]:
                    answer[s] = cost
    
    # Update the answer for k=0 to ensure non-empty set
    # Also, handle cases where adding multiple exponents results in a better cost
    
    for s in range(N):
        if answer[s] == INF:
            # Try combinations of multiple exponents, but this is not covered
            answer[s] = -1  # but the problem states it's possible
    
    # Finally, output the answer
    for k in range(N):
        print(answer[k] if answer[k] != INF else -1)

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

if __name__ == "__main__":
    main()
0