AtCoder Beginner Contest 178

D問題 Redistribution

気づき

制約が小さい（ $<2000$ ）
長さが1のときは1通り

modを取りながらの除算（逆元）とコンビネーションは持っている前提とする。
公式解説はDPなので、ここでは単純に高校数学範囲のでやる。

項の和が $S$ となる数列 $A$ の長さを $L$ とする。
まずは数列 $A$ の長さがどこまで大きくなれるか考えると、すべての項が3以上なので、配列の長さは最大で $\lfloor \frac{S}{3} \rfloor$ となる。

次に、 $A$ の長さを増やしていったとき何が起こるか考察する。
$L=1$ のとき、 $A=[S$ ]の1通り。
$L=2$ のとき、それぞれの項が3以上は確定しているので、残りの $S - L \times 3$ をどう分配するかという問題になる。
これは「区別の出来ないボールが $S - L \times 3$ 個、区別のできる箱が $L$ 個あるとき、全てのボールを箱に入れる方法は何通りあるか？」という問題と考えることができる。
重複組合せと呼ばれるもので、仮に重複組合せという言葉を忘れていても、「ボールと仕切りの並び替え」を考えれば、組み合わせの応用で解くことができる。
以上より、 $L=1,2,3,4...$ と見ていき、それぞれについて重複組合せを求めて足し合わせれば良い。
よって $0 < i \le \lfloor \frac{S}{3} \rfloor$ について、 ${{}_{S - L \times 3} H_i }$ を足し合わせることで解ける（ $i=1$ のときも重複組合せは $1$ になるのでOK）（0通りの場合に注意）。