arc060 a

arc060_a

2^50なので無理

2^50通りについてAに一致するか判断するより緩めた方が良い？

Aは与えられるのでとりあえずAを引いて符号でわける

でも2^25でも厳し目かな、最悪ケースは2^49だしな

2^49について和を求めるのは辛いが、値域は高々50×49なので値域と定義域の交換をしよう

和→頻度にすればいいね、頻度表

下の頻度表をL、上の頻度表をU、0の個数をZとすればLi×Ri×2^Zだ

一枚も選ばないケースが含まれるので-1すること

計算量

Nで符号で分割

N^3でDPで頻度表を作る

N^2で頻度表の突き合わせ

公式解説

Aを引くことによって目的を「和が0」にし、カードの枚数に関係なくすることがオーダーを減らす手であった

「和が0」を僕は2つの頻度表の突き合わせで数えたが、公式解法はまとめてDPして0になるところを見る