数え上げの対象となる数列の長さを固定します。

長さが \(k\) であり、すべての項が \(3\) 以上の整数で、その総和が \(S\) であるような数列の個数は、長さが \(k\) であり、すべての項が \(0\) 以上の整数で、その総和が \(S-3k\) であるような数列の個数と等しいです。

そのような数列の個数は、互いに区別できない \(S-3k\) 個のボールと互いに区別できない \(k-1\) 個の仕切りの並び替え方の総数に等しいので、全部で \( _{(S-3k)+(k-1)}C_{k-1} = {}_{S-2k-1}C_{k-1} \) 個あります。

\(k\) の取り得る値は \(k = 1,2,\ldots, \lfloor \frac{S}{3} \rfloor\) なので、結局この問題の答えの値は以下のようになります。

\[\sum_{k=1}^{\lfloor \frac{S}{3} \rfloor} {}_{S-2k-1}C_{k-1}\]

二項係数の値の前計算に \(O(S)\) 、答えの式の計算に \(O(S)\) かかるので、全体で \(O(S)\) でこの問題の答えを求めることが出来ます。