No.616

数列は相異なるので座標圧縮して $0, 1, \dots, n-1$ にする. この数列は $n$ が決まれば決まるので, 実は数列は読まなくてもいい.

$i$ 番目の要素は $0$ から $i$ の転倒数を持つことができ, $i$ 番目までの和が $j$ となる組み合わせの数を $A(i, j)$ とすると,

$$A(i, j) = \sum_{k=j-i}^j A(i-1, k)$$

となる.

これを愚直に計算すると $O(NK^2)$ となって間に合わないが, $A(i, j)$ の累積和を都度計算することにより $O(NK)$ で計算できるようになる.