[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)\).