我们首先尝试挖掘这个分组的性质。
我们发现，我们可以把在同一个组的夫妻和不在同一个组的夫妻分开来处理。
这里，分开之后我们只需要让一种情况有顺序，另外一种不能有顺序。如果两个没有顺序 / 有顺序的序列合并，一定会出现漏算 / 多算。
所以为了方便，我们可以把第二种情况看作有顺序。
思考：为什么不能把第一种情况看作有顺序呢？
首先假设总共有 \(i\) 组，这里 \(i\) 是我们枚举的数。
\(\text{Situation 1}\)：同一个组的夫妻情况数
假设有 \(x\) 组这种夫妻。
我们需要把这 \(x\) 组夫妻划分进不同的组别里，组内没有顺序，组外也没有顺序。
抽象化一下，我们需要把 \(x\) 个互不相同的数分组，组内、组外均没有顺序。
仔细思考，这不是第二类斯特林数吗？直接 \(f_{i, j} = f_{i - 1, j - 1} + j \times f_{i - 1, j}\) 实现 \(\mathcal{O}(n^2)\) 递推即可。
\(\text{Situation 2}\)：不同组的夫妻情况数
这非常容易。
由于我们固定了这种情况有顺序，所以我们完全可以对每一个夫妻单独划分组别。每一个夫妻的方案数为 \(i \times (i - 1)\)，即总方案数为 \(p_{i, x} = (i(i - 1))^x\)。
接下来合体。
在预处理完前两个的情况后，我们首先枚举 \(i\) 表示整体的组别数量。
接着，我们枚举分在同一组的夫妻 \(j\)。于是，\(n - j\) 对夫妻不在同一组。这样的方案数显然是 \(\binom{n}{j}\)。
再结合开头的结论，我们得出答案：
\[\sum_{i = 1}^n \sum_{j = 1}^i \binom{n}{j} \times f_{i, j} \times p_{i,j} \]感觉非常的数学。值得记录。
标签：月赛,顺序,组别,题解,T3,times,枚举,夫妻,我们 From： https://www.cnblogs.com/aemmprty/p/18176176