D - Sets Scores 解説 by evima
[1] Fixing the common elements
It is difficult to handle the condition that the number of elements contained in exactly one of \(S_i\) and \(S_{i+1}\) is \(1\), so let \(X_i\) be that element contained in exactly one of \(S_i\) and \(S_{i+1}\).
Below, we consider the problem for fixed \(X_1,X_2,\dots,X_{N-1}\).
[2] Solving the fixed case
Determining \(S_1\) will also determine \(S_2\) and all subsequent sets, so there are \(2^M\) possible brilliant sequences of sets.
Let \(A_x\) be the number of sets containing \(x\) when \(S_1\) contains \(x\), and \(B_x\) be the number of sets containing \(x\) when \(S_1\) does not contain \(x\).
Then, the sum of the scores for all possible choices of \(S_1\) is \((A_1+B_1)(A_2+B_2)\dots(A_M+B_M)\), which equals \(N^M\) since \(A_i+B_i=N\).
[3] Finding the whole sum
There are \(M^{N-1}\) choices of \(X\), each of which yields the total score of \(N^M\), so the answer is \(N^M \times M^{N-1}\).
Therefore, the problem is solved in \(\mathrm{O}(\log N + \log M)\).
投稿日時:
最終更新: