核心思想
一类奇奇怪怪的容斥，解决形如：
- 对 \(k\) 个计数对象计数，且这 \(k\) 个计数对象是无序的。
这类问题的难点就在无序上，因为对于某种方案，它会被计算 \(\frac{k!}{\prod {a_i!}}\) 次，其中 \(a_i\) 是数字 \(i\) 出现的次数。我们无法除掉通过某个简单的东西来得到最终结果。
考虑枚举这 \(k\) 个数的集合划分（不难得到总方案数是贝尔数），并且钦定同一个集合里面的数相同，不同集合里面的数不同。对于每个划分 \(p_1,p_2...p_m\) 算出方案数之后，就只需要对方案数除掉 \(\prod{a_i!}\) 即可，其中 \(a_i=\sum_j [|p_j|=i]\) 。
接下来对于某个划分 \(p_1,p_2...p_m\)，考虑用容斥求它的方案数。一种朴素的方法是用 \(O(2^{\frac{m(m-1)}{2}})\) 的时间复杂度来钦定每对划分是否相等，对于没有钦定的情况它们是任意的，钦定完之后实际上我们得到的就是一个朴素的序列问题。
显然上述容斥的复杂度十分高，考虑优化。我们把 \(p_1,p_2...p_m\) 抽象成点，钦定它们是否相等抽象为边，那么朴素的枚举方法就是枚举每条边存不存在，然后同一个连通块的点必须相同，不同连通块则没有要求。考虑直接枚举连通块，也就是对 \(p_1,p_2...p_m\) 再做一遍集合划分，设划分成 \(q_1,q_2...q_n\)，划分在相同集合的 \(p\) 强制钦定相同。考虑某种划分的容斥系数，显然就是 \(\sum_{G_1 \text{是} |q_1| \text{个点的连通图}}(-1)^{e(G_1)}...\sum_{G_n \text{是} |q_n| \text{个点的连通图}}(-1)^{e(G_n)}\)，其中 \(e(G)\) 是图 \(G\) 的边数。显然求和之间是独立的，可以直接简化为 \(\prod g(q_i)\)，其中 \(g(x)\) 表示 \(\sum_{G_1 \text{是} x \text{个点的连通图}}(-1)^{e(G_1)}\)。
考虑计算 \(g\)，通过常识，设 \(f(x)\) 为 \(x\) 个点的任意图的容斥系数和，即 \(f(x)=\sum_{i=0}^{\frac{x(x-1)}{2}}{\frac{x(x-1)}{2}\choose i}=[x=1]\)。枚举 \(1\) 号点所在连通块的大小，则有 \(f(x)=\sum_{i=1}^x{x-1\choose i-1}g(i)f(x-i)\)。代入 \(f\) 后不难发现只有 \(g(x)\) 和 \(g(x-1)\) 在式子中，整理即 \(g(x)=(-1){x-1\choose x-2}g(x-1)\)，\(g(1)=1\)，归纳不难得到 \(g(x)=(-1)^{x-1}(x-1)!\)。
至此，我们把容斥的复杂度从 \(O(2^{\frac{m(m-1)}{2}})\) 优化到了第 \(m\) 个贝尔数的复杂度。
再次优化
不难发现总复杂度大概是一个“贝尔数的贝尔数”的复杂度，尽管已经较优，但是还是可以优化。
考虑把第一个集合划分从第 \(m\) 个贝尔数的复杂度优化到第 \(m\) 个划分数的复杂度，也就是说我们现在枚举的划分是无序的，我们需要把所有有序的位置分配给这些划分。首先我们把所有有序的位置全排列，方案数是 \(k!\)，再考虑除掉一些同构的情况。假设我们的划分是 \(p_1,p_2...p_m\)，那么我们首先要除掉 \(\prod p_i!\)，因为划分内部是无序的，其次我们还需要除掉 \(\prod a_i !\)，其中 \(a_i=\sum_j [p_j=i]\)，因为划分之间也是无序的。这样就可以求得所有的方案了。
可以发现的是，如果我们现在对计数加一个条件——这 \(k\) 个计数对象不仅无序，而且两两不同。那么它就没有第一个集合划分的复杂度，并且容斥部分可以直接使用上述优化，总复杂度就被优化到了大小为 \(k\) 的划分数。
而对于没有两两不同限制的情况，我们依旧可以通过这个优化把时间复杂度优化到“划分数的贝尔数”。当然，在容斥部分我们也可以搜划分数，然后用状压 DP 去计算，直觉上复杂度是比贝尔数要优的，但暂时还不会具体的分析。