結果

問題 No.2062 Sum of Subset mod 999630629
コンテスト
ユーザー lam6er
提出日時 2025-04-15 23:38:18
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 912 bytes
コンパイル時間 364 ms
コンパイル使用メモリ 81,672 KB
実行使用メモリ 79,136 KB
最終ジャッジ日時 2025-04-15 23:39:32
合計ジャッジ時間 7,616 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 8 TLE * 1 -- * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 998244353
m = 999630629

def main():
    import sys
    input = sys.stdin.read().split()
    N = int(input[0])
    A = list(map(int, input[1:N+1]))
    sum_A = sum(A)
    
    # Compute sum_subset_sums
    pow2_Nminus1 = pow(2, N-1, MOD)
    sum_subset_sums = sum_A % MOD * pow2_Nminus1 % MOD
    
    if sum_A < m:
        print(sum_subset_sums % MOD)
        return
    
    T = sum_A - m
    B = [a for a in A if a <= T]
    sum_B = sum(B)
    len_B = len(B)
    
    if sum_B <= T:
        K = pow(2, len_B, MOD)
    else:
        # Initialize DP
        dp = [0] * (T + 1)
        dp[0] = 1
        for a in B:
            for s in range(T, a - 1, -1):
                dp[s] = (dp[s] + dp[s - a]) % MOD
        K = sum(dp) % MOD
    
    answer = (sum_subset_sums - m % MOD * K) % MOD
    # Ensure non-negative
    answer = (answer + MOD) % MOD
    print(answer)

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