题解

思路

先固定相邻集合间发生变化的元素序列，共有 $M^{N-1}$ 种。

做法

再枚举初始集合 $S_1$，整个集合序列便被唯一确定。对某个元素 $x$，若它在初始包含 $x$ 时一共出现 $c_x$ 次，那么初始不包含 $x$ 时恰好出现 $N-c_x$ 次，因为两种状态在每个位置完全互补。

对所有初始集合求得分和时，可以按元素使用分配律独立求和，每个元素的两种初态贡献之和都是 $c_x+(N-c_x)=N$，所以固定变化序列后的总贡献恒为 $N^M$。乘上变化序列数量，答案为 $N^M M^{N-1}$。

复杂度

用二进制快速幂计算，时间复杂度为 $O(\log N+\log M)$，额外空间复杂度为 $O(1)$。