Predilection

問題

操作後の列は、元の数列をいくつかの区間に分けて区間内の総和を並べた列

例: (3, 1, 4, 1, 5, 9) -> ((3, 1, 4), (1), (5, 9)) -> (8, 1, 14)

もし A_i ≧ 1 だったら区間の分け方 2^(N-1) 通りと操作後の列が一対一 (たぶん)

一般には、操作後の列は区間の分け方より少ない

たとえば、元の数列が (1, 2, 2, -1, -1, 3, 3) のとき (1, 2, 3, 3) をつくるには

((1), (2, 2, -1, -1), (3), (3))

((1), (2), (2, -1, -1, 3), (3)) ★

の2通りあるように、異なる区間の分け方が同じ列 (1, 2, 3, 3) になりうる

A_{i-1} までで作った区間和の列が b_1, ..., b_k のとき、A_i の使い方は次の2通り

1: b_1, ..., b_k, A_i

2: b_1, ..., b_k + A_i

実際は ★ の分を多く数えてるので引く

これは、上の例における (1, 2, 0) の作り方の数を引けばよく、

添字の±1に注意して実装する

提出