ARC096C Everything on It

题意：有 种酱。你需要若干碗拉面，可以在每碗拉面上放若干种酱，也可以不放（可能的拉面种类为 ）。

拉面集合需要满足：

• 不能出现酱一样的两碗拉面。
• 每一种酱至少在两碗拉面中加了。

求拉面集合的方案数。答案对给定的质数取模。

，时限 。

---

考虑容斥，设 表示钦定 种酱不合法的方案数。

首先选出不合法的酱，方案数为 。

首先将 种不合法的酱安排到 碗拉面中。

设 为 种酱安排到 碗拉面，每种都出现最多一次的方案数。

不难联想到一个很类似的数：第二类斯特林数 ,表示将 个球放入无区别的 个盒子，所有盒子都非空的方案数。

不同点在于，斯特林数中每个球必须投放一次，而 中可以不投放。

考虑新建一个盒子当垃圾桶，但是垃圾桶又只能非空，于是新建一个 号球，钦定这个球所在的盒子为垃圾桶。

这就能得到 。

接下来考虑其他 种酱料随意选择的方案数。

可以组成 种拉面，每种又可以出现或不出现，方案数为 。

此外，这些酱还能往前面的 碗里面加，方案数为 。

答案为 ，即：

计算幂的幂时需使用费马小定理。

复杂度 。