注：この解法は見た目がきれいなだけで、この言い換えをせず(この解法と同等なことを \(a\) に注目したまま考えることでも)自然に解けます。

\(S=\sum_i a_i\)とする。数列の値の並び順は操作に影響しないため、\(a\) は降順にソートされているとしてよい。数列 \(a'\) を \(a'_i=a_i-a_{i+1},\ a'_N=a_N\) により定める。 \(a\) のかわりに \(a'\) に対する操作を考えると

• 最も後ろにある \(0\) でない要素を \(1\) 小さくする
• 末尾の要素を \(1\) 大きくする

になる。したがって、数列 \(a'\) から作れる数列は \((a'_1,\ldots,a'_{k-1},*,0,\ldots,0,*)\) のような形になっている。

より正確には、数列 \(a'\) に対して操作をして数列 \(b'\) が作れるための必要十分条件は次のようになる。

• ある \(1\leq k\leq N+1\) が存在して、次が全て成り立つ
  • \(i< k\) を満たす全ての \(i\) で \(b'_i=a'_i\)
  • \(0\leq b'_k< a'_k\)
  • \(k< i <N\) を満たす全ての \(i\) で \(b'_i=0\)
  • \(\sum_i ib'_i \leq S\)

\(4\) つ目の条件は石の個数の総和に関する条件である。

\(k=N,N+1\) のケースは明らかである。そうでないときを考える。

\(k\) と \(b'_k\) を固定すると自由度があるのは \(b'_N\) のみであり、このとき \(4\) つ目の条件から、\(b'_N\) の取りうる値の範囲は \(\displaystyle 0\leq b'_N \leq \left\lfloor\frac{(S-\sum_{i=1}^{k-1}ia'_i)-kb'_k}{N}\right\rfloor\) となる。よって、\(k\) を固定したときありえる数列の個数は \(\displaystyle \sum_{x=0}^{a'_k-1}\left(\left\lfloor\frac{(S-\sum_{i=1}^{k-1}ia'_i)-kx}{N}\right\rfloor+1\right)\) であり、これはfloor_sumそのものである。