[1]条件の固定

\(S_i\) と \(S_{i+1}\) のどちらかにのみ含まれる要素の個数が \(1\) 個という条件が扱いにくいので、\(S_i\) と \(S_{i+1}\) のどちらかにのみ含まれる要素を \(X_i\) とします。

今後、\(X_1,X_2,\dots,X_{N-1}\) が固定されたときについて問題を考えます。

[2]固定された問題を解く

\(S_1\) を決めれば \(S_2\) 以降も全て決まるため、あり得る「素晴らしい集合の列」は \(2^M\) 通りあります。

もし \(S_1\) に \(x\) が含まれるときの \(x\) を含む集合の個数を \(A_x\)、\(S_1\) に \(x\) が含まれないときの \(x\) を含む集合の個数を \(B_x\) とします。

ここで、\(S_1\) を全通り動かしたときのスコアの総和は \((A_1+B_1)(A_2+B_2)\dots(A_M+B_M)\) です。\(A_i+B_i=N\) が成り立つため、この値は \(N^M\) となります。

[3]全体の解を求める

\(X\) の個数は \(M^{N-1}\) 個あり、この全てについてスコアの総和が \(N^M\) であるため解は \(N^M \times M^{N-1}\) です。

よって、本問題を \(\mathrm{O}(\log N + \log M)\) で解くことができます。