arc096C | Everything on it

link

不解释题意。

---

我肯定是作麻烦了，我冷静一下。。

这题花了我一个下午。。。

好你马气人。

把限制列出来 ：

1. 任意两个子集互不相同
2. 1,2,3...n 每个至少出现2次。

容斥是很朴素的想法，考虑第一个不好容斥，第二个相对更好容斥。

我们现在转化成 钦定 \(j\) 个地方出现次数少于 \(1\)。

可以写出下面这个式子，我会解释每一项的含义。 \[ \sum_{j\ge 0}(-1)^j\binom{n}{j}\sum_{k=0}^{j}\sum_{t=0}^{k}\binom{j}{k} \begin{Bmatrix} k\\t \end{Bmatrix} 2^{2^{n-j}}\times(2^{n-j})^t \]

1. 首先 \(j\) 是钦定少于1次的位置个数。

2. \(\binom{n}{j}\) 代表从 \(n\) 个中选 \(j\) 个作为钦定的。

3. k枚举的是恰好使用1个的被钦定的位置。

4. t枚举的是有多少个集合使用这k个位置。

5. \(\binom{j}{k}\) 含义是得从钦定的 \(j\) 个选出使用的 \(k\) 个。

6. \(\begin{Bmatrix}k\\t\end{Bmatrix}\) 含义是把这 \(k\) 个位置无序划分给这 \(t\) 个集合。

   到此，我们已经成功的把钦定位置的集合关系确定好了。

7. \(2^{2^{n-j}}\) 代表剩下没有钦定的位置能组成 \(2^{n-j}\) 个不同集合，每个集合都可以选。

8. \((2^{n-j})^t\) 含义是我们给这 \(t\) 个无序集合，定下来他们在非钦定位置中集合关系。这样不会产生重复的集合。因为你的斯特林数是划分成非空集合。

这样我们这道题就做完 90%了。

我的做法十分无脑，我把斯特林数拆开了。。。。。

正确的处理方法是用组合意义把这样一个东西 \[ \sum_{k=0}^{j}\binom{j}{k}\begin{Bmatrix} k\\t \end{Bmatrix}=\begin{Bmatrix} j+1\\t+1 \end{Bmatrix} \] 这个考虑放一个垃圾桶专门收空元素。这个真不会硬推了,kk