[AtCoder] ABC 178 D – Redistribution

問題

方針

\( a_i \) を非負整数として、次の方程式を考えます。

\[ a_1 + a_2 + \cdots + a_n = S – 3n\]

上記を満たす \( a_i \) の組み合わせは、\( k = S – 3n \) として、

\[ {}_{k + n – 1} \mathrm{ C }_{n – 1}\]

個あります。したがって、\( 1 \leq n \leq \left \lfloor \dfrac{S}{3} \right \rfloor+ 1 \) の範囲で全探索します。

コード