ARC147D Sets Scores 做题记录

构造 $N$ 个集合，$S_1$ 到 $S_N$ 。

每个集合满足以下条件：

• 每个元素是不大于 $M$ 的正整数；
• 对于两个相邻的集合 $S_i$ 和 $S_{i+1}$，有且仅有一个数恰好在这两个集合中的一个里出现。

定义这 $N$ 个集合的分数为 $\prod\limits_{i=1}^m cnt(i)$ ，其中 $cnt(i)$ 为 $i$ 在所有 $N$ 个集合中出现的次数。

求所有满足条件的集合簇的分数之和，答案对 $998244353$ 取模。

$1\le N,M\le 2\times 10^5$ 。

不难发现，元素是互相独立的，所以考虑某个元素 $x$ 的情况，设 $f(x)_i=[x\in S_i]$，那么 $f(x)$ 一定是一个形如 $[0,0,1,1,0,1]$ 这样的 $01$ 数组。

容易发现，由于有且仅有一个元素只被相邻的 $S_i,S_{i+1}$ 中的一个包含，设这个元素为 $val_i$。由于 $val_i=x$ 的 $val_i$ 已经确定了下来，不能再给别的元素用，所以当 $pos_x=\{i|val_i=x\}$ 相同时，这两种方案对于其它元素来说是本质相同的。

观察到 $val_i=x$ 当且仅当 $f(x)_i\not=f(x)_{i+1}$，所以若给 $f(x)$ 取反，即 $1$ 变成 $0$，$0$ 变成 $1$，$pos_x$ 是不变的，所以其它元素出现次数的乘积也不变，设这个值为 $V$。假设取反之前 $f(x)$ 中有 $a$ 个 $1$，取反之后显然有 $n-a$ 个，取反之前的答案是 $V\cdot a$，取反之后的答案是 $V\cdot (n-a)$，总的答案是这两部分的加和，观察到加和就是 $nV$，所以元素 $x$ 对乘积的贡献就是 $n$。那么每种本质不同的方案的答案加起来就是 $n^m$。

考虑计算本质不同的方案数，显然所有方案数是 $2^mm^{n-1}$，因为 $S_1$ 可以任意选，之后的 $S_i$ 和 $S_{i-1}$ 只能有一个元素的差异。那么由于每种元素本质相同的方案都会算两次，所以本质不同的方案数就是 $\frac{2^mm^{n-1}}{2^m}=m^{n-1}$，答案即为 $n^mm^{n-1}$。