コイン \(1\) 枚に対して \(1\) 枚のカード（正の値が書いてある）を一意に対応させられる． 移動の様子を考えると

\(0 \to\) 負 \(\to\) コインに対応すると決めたカードでジャンプ \(\to\) 正 \(\to 0\) という形になる．

負，正と書いてある部分が空というケースもある．

合計でコインを \(k\) 枚獲得すると決め打つ． 対応するカードの集合と順番も決め打つ． 各カード \(i\) について，\(x_i \to x_i+A_i\) という移動をするわけだが，この \(x_i\) も決め打つ． \(x_i\) は \(A_i+1\) 通りあるわけだが，実はどれを選んでもあとの数え上げで答えが変わらないことがわかる．

ここでまず，\(-1,\cdots,-1,A_i,-1,\cdots,-1\) (\(A_i\) の前には \(|x_i|\) 個の \(-1\), 後ろには \((A_i-|x_i|)\) 個の \(-1\)) という列が部分列として必ず必要だとわかる． これを \(k\) 個連結した列を骨組みとして，残りのカードを適切に入れていくことで操作列を作る．

コインと対応させた \(k\) 枚のカードの値の総和を \(T\) とすると，骨組みに使っていないカードの入れ方は \(T,k\) だけから計算できる． イメージとしては骨組みに適切なパターンを挿入することを考える． パターンというのは，「常に非負領域を動き，総和が \(0\) の操作列」である．非負の変わりに非正を動く操作列も必要に思えるが，これは列の reverse で一対一に対応するので同一視して考えて良い．

コインと対応していない \(S-k\) 枚のカードを円環に並べてみると，\(T\) 個の \(-1\) と \(T\) 個のパターンに一意に分解可能である．これらのパターンをそのまま骨組みに挿入すると最終的な操作列が得られる． このままだとパターンの円環列を数えてしまうが，これを列の個数にするためには単に \(T\) をかければよい．

以上のアルゴリズムを素直に実装すれば \(O(N^2)\) 解法が得られる．

実装例