AtCoder上にある問題のうち、AtCoder Problemsでdiff 800以上と判定されているものを順番に解いていく企画。
基本的な考え方は全てコード中のコメントに入れてあるので、参照のこと。
出典:
AtCoder Regular Contest 116 B – Products of Min-Max
Aの空でない部分列Bは


個ありますとか見た瞬間に、ヤバい香りしかしない問題ではある。
数学力が高い人は公式解説で理解できるのだと思うが、僕のように数学力が0の人は、Σ記号を見るだけで頭痛がすることだろう。
というわけで、かなり噛み砕いた考え方をコメントに入れてあるので、参考にしてみてもらいたい。
def main():
N = int(input())
A = list(map(int, input().split()))
MOD = 998244353
A.sort()
result = 0
for i in range(N):
result = (result + A[i] ** 2) % MOD
mult = 0
for min_i in range(N-2, -1, -1):
mult = (mult * 2 + A[min_i+1]) % MOD
result = (result + A[min_i] * mult) % MOD
print(result)
main()
関連