E - Sum of Square of Sum 解説 by spheniscine 印刷ページ

Alternative Solution

Replace the balls in the original problem with buckets. Each bucket \(i\) has \(A_i\) balls, all distinguishable.

The sum in the original problem is then equal to the number of ways of first choosing \(K\) buckets from the \(N\) buckets, then choosing balls among the chosen buckets twice (possibly choosing the same ball twice).

We can then swap the summation, such that it becomes first choosing balls twice among all the buckets, then counting how many possible choices of buckets will allow us to choose those balls.

Quite obviously, we must choose the bucket(s) that we chose the ball(s) from. If the balls chosen are from the same bucket, there are \(\large\binom {N-1}{K-1}\) ways to choose the remaining buckets. If the balls chosen are from two different buckets, there are \(\large\binom {N-2}{K-2}\) ways (we consider this to be \(0\) if \(K < 2\)).

Therefore we can compute the answer via the formula:

\[\sum_{i=1}^N {A_i \left(A_i {\small\binom{N-1}{K-1}} + (\Sigma_A - A_i){\small \binom{N-2}{K-2}} \right)}\]

where the binomial values as well as \(\Sigma_A := \sum_i A_i\) are all precalculated, in \(O(N)\) time.

投稿日時:
最終更新: