RainAir
My OI Blog
RainAir
ARC096E - Everything on It

题意

求有多少个子集族,满足:
1. 其中任意一个子集都是 $[n]$ 的子集;
2. 任意两个子集互不相同;
3. $1,2,\cdots ,n$ 都在其中至少出现了 $2$ 次。

答案对 $M$ 取模。
$2 \leq N \leq 3000,10^8 \leq M\leq 10^9 +9$,$M$ 是质数。

题解

dyls 说:看到子集族先想到容斥https://blog.aor.sd.cn/wp-content/uploads/2019/02/20181230193958416.png我太菜了
考虑容斥:现在我们是需要数限定一些数只能出现 $0$ 或 $1$ 次,其他数随意出现的方案数。数之间是没有顺序的,所以可以只枚举这样的数的个数,然后计算。令 $g_i$ 表示有 $i$ 个数只能在子集族的元素中出现 $0$ 或 $1$ 次,其他数无限制的方案数,那么答案就是:
$$2^{2^n} – \sum_{i=1}^n (-1)^i \binom n i g_i$$
现在我们考虑如何去算出 $g_i$,一开始的想法可能是去枚举有多少个出现了 $0$ 次,多少个出现了 $1$ 次,然后我们发现我们并不知道有哪些子集可以包含它,但是注意到这题只需要 $O(n^2)$ 的做法,所以我们可以考虑去枚举有多少个子集包含这些数。设有 $j$ 个子集包含了,那么现在的子集族由两部分组成:一部分是子集内全是无限制的数的集合,另一部分是子集内有限制的集合。前一种的贡献显然是 $2^{2^{n-i}}$,后一种的贡献大概就是考虑被限制的数应该被分到这些集合中,但是要注意有些数可以不出现,所以我们可以新建一个集合来表示不出现的数,也就是 $\left \{^{i+1}_ {j+1} \right \}$,然后发现无限制的数也可以加入到这些集合中,所以还有贡献 $(2^{n-i})^j$。
所以 $g_i$ 的计算过程就十分明了了!:
$$g_i = \sum_{j=0}^i 2^{2^{n-i}}\left \{^{i+1}_ {j+1} \right \}(2^{n-i})^j$$
预处理一下卡卡常就过去了。

代码

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/898
如文中无特殊声明,本文采用 CC BY-NC-SA 4.0 进行许可,转载请说明出处!
希望 CSP 不要翻车,希望省选不要翻车
https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=256&d=mm&r=g

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

RainAir

ARC096E - Everything on It
题意 求有多少个子集族,满足: 1. 其中任意一个子集都是 $[n]$ 的子集; 2. 任意两个子集互不相同; 3. $1,2,\cdots ,n$ 都在其中至少出现了 $2$ 次。 答案对 $M$ 取模。 $2 \leq N \le…
扫描二维码继续阅读
2019-10-18
标签
近期评论