施工中。。。
计数
基础知识
容斥原理
子集反演
二项式反演
卡特兰数 / 反射容斥
斯特林数 / 斯特林反演
矩阵树定理 *
BEST定理 *
Prufer序列 *
(* : NOIP 用不到,鸽一下)
基础知识
对称恒等式
上指标求和
平行求和法
- 证明\[\begin{align*}\sum_{k=0}^{n}\binom{m+k}{k}&=\sum_{k=0}^{n}\binom{m+k}{m}+0\\ &=\sum_{k=m}^{n+m}\binom{k}{m}+\sum_{k=0}^{m-1}\binom{k}{m}\\ &=\sum_{k=0}^{n+m}\binom{k}{m}\\ &=\binom{n+m+1}{m+1}=\binom{n+m+1}{n} \end{align*} \]
范德蒙德卷积
Lucas 定理
容斥原理
设全集 \(U\) 有 \(n\) 种不同的属性,拥有第 \(i\) 种属性的元素构成集合 \(X_i\)。
集合的交可以用全集减去补集的并集计算(其实本质就是德摩根定理):
P3813 [FJOI2017] 矩阵填数
题目描述:
给定一个 \(h \times w\) 的矩阵,矩阵的行编号从上到下依次为 \(1 \sim h\),列编号从左到右依次 \(1 \sim w\)。
在这个矩阵中你需要在每个格子中填入 \(1 \sim m\) 中的某个数。
给这个矩阵填数的时候有一些限制,给定 \(n\) 个该矩阵的子矩阵,以及该子矩阵的最大值 \(v\),要求你所填的方案满足该子矩阵的最大值为 \(v\)。
现在,你的任务是求出有多少种填数的方案满足 \(n\) 个限制。
设 \(X_i\) 表示第 \(i\) 个子矩阵最大值为 \(v_i\) 的填数状态的容斥集。
发现我们在求 :
这个东西等于:
直接容斥:
CF1821F Timber
题目描述:
问题要求计算在一条有 \(n\) 个位置的小巷中种植 \(m\) 棵高度为 \(k\) 的树,使得砍树时每棵树可以向左或向右倒下,但不会倒在位置 \(0\) 以及位置 \(n+1\),且每个位置最多被一棵树占据的种树方案数。
设全集 \(U\) 表示所有“初始方案”的集合,其中每个方案包括两个步骤:
- 选择 \(m\) 个代表元(左端点),使得当所有树向右倒时,区间不重叠。代表元的选择方案数为 $ \binom{n - mk}{m} $。
- 为每棵树分配一个倒下方向(左倒或右倒),有 \(2^m\) 种分配方式。
因此,全集的大小为:
然而,这种初始方案会重复计算那些既能左倒又能右倒的树。具体来说,如果一棵树既能左倒又能右倒,则在初始方案中它被计算了两次(一次左倒,一次右倒),但实际种树方案中只应计算一次。因此,我们需要从 \(U\) 中排除那些至少有一棵树具有两种倒下方向的方案。
对于每棵树 \(i\)($i = 1, 2, \dots, m $),定义子集 \(A_i \subseteq U\),表示树 \(i\) 具有两种倒下方向的方案集合。树 \(i\) 具有两种倒下方向时,它占据的区间为 \([x_i - k, x_i + k]\)(长度为 $ 2k+1$)。
因此,当有 \(i\) 棵树具有两种倒下方向时,代表元的选择方案数为 $\binom{n - (m+i)k}{m} $,并且这些 \(i\) 棵树不再有倒下方向的选择(因为它们已确定两种方向),而剩余的 $ m-i $ 棵树各有两种倒下方向选择。
对于任意索引集 \(I \subseteq \{1, 2, \dots, m\}\) 且 $ |I| = i $,定义 \(A_I = \bigcap_{j \in I} A_j\),表示所有树 \(j \in I\) 都具有两种倒下方向的方案集合。则:
由于有 $ \binom{m}{i} $ 个这样的索引集 \(I\),所以所有 $ |I| = i $ 的交集大小之和为:
根据容斥原理,没有树具有两种倒下方向的方案数为:
(其中当 $ i = 0 $ 时,$ \sum_{|I|=0} |A_I| = |U| $。)
因此:
当然这个题还有一个很显然的二项式反演的解法,这里做 Bonus 给读者自行思考。
子集反演
PS : 后者应当是超集反演。
P3349 [ZJOI2016] 小星星
题目描述:
小 Y 是一个心灵手巧的女孩子,她喜欢手工制作一些小饰品。她有 \(n\) 颗小星星,用 \(m\) 条彩色的细线串了起来,每条细线连着两颗小星星。
有一天她发现,她的饰品被破坏了,很多细线都被拆掉了。这个饰品只剩下了 \(n-1\) 条细线,但通过这些细线,这颗小星星还是被串在一起,也就是这些小星星通过这些细线形成了树。小 Y 找到了这个饰品的设计图纸,她想知道现在饰品中的小星星对应着原来图纸上的哪些小星星。如果现在饰品中两颗小星星有细线相连,那么要求对应的小星星原来的图纸上也有细线相连。小 Y 想知道有多少种可能的对应方式。
设
\(f(S)\) : \(n\) 个点的映射恰好使用了 \(S\) 中的所有点。
$g(S) $ : \(n\) 个点的映射至多只能够使用 \(S\) 中的点。
显然:
反演后可得:
此时我们只需要知道如何求解 \(g\) ,设 \(dp(x,j,S)\) 为点 \(x\) 映射为 \(j\) , \(x\) 的子树中至多只能使用 \(S\) 中的点作为映射值的方案数。
显然 :
\(dp(root,i,S)\) 可以 \(O(n^2)\) 求解。
时间复杂度 $ O(n32n)$ 。
Atcoder AGC005D ~K Perm Counting
题目描述:
Snuke 非常喜欢排列,所以他决定创建一个长度为 \(N\) 的排列。
但是 Snuke 不喜欢整数 \(K\),因此他决定创建一个满足以下条件的排列:
- 设排列为 \(a_1, a_2, ..., a_N\)。对于所有的 \(i = 1,2,...,N\),满足 \(|a_i - i| \neq K\)。
长度为 \(N\) 的排列共有 \(N!\) 种,其中满足条件的有多少种?
设 \(W(S)\) 表示 \(|P_i - i| = k\) 的位置构成的集合 包含 \(S\) 的方案数。
设 \(w(S)\) 表示 \(|P_i - i| = k\) 的位置构成的集合 恰好 为 \(S\) 的方案数。
反演后可知答案为:
发现任意 \(W(S)\) 都能写成 \((n-|S|)! \times W'(S)\),因为除开钦定的 \(x\) 个元素外,其它的元素可以任意排列。
设:
则:
\(f(i)\) 在这里的实际意义是对大小为 \(i\) 的集合统计只考察钦定的 \(i\) 个元素的排列方案数的总和。
\(f\) 可以通过各种方式讨论出来,这里留给读者自行思考。
二项式反演
P5505 [JSOI2011] 分特产
题目描述:
把 \(m\) 种特产分给 \(n\) 个同学,第 \(i\) 种特产有 \(a_i\) 个,要求每个同学必须分到至少一个特产,求方案数对 \(10^9+7\) 取模。
设 \(f(k)\) 表示钦定至少 \(k\) 个同学没有分到特产, \(g(k)\) 表示恰好 \(k\) 人没有分到特产。
显然:
反演:
\(f\) 的计算就很显然了:
P6478 [NOI Online #2 提高组] 游戏
题目描述:
小 A 和小 B 正在玩一个游戏:有一棵包含 \(n=2m\) 个点的有根树(点从 \(1\sim n\) 编号),它的根是 \(1\) 号点,初始时两人各拥有 \(m\) 个点。游戏的每个回合两人都需要选出一个自己拥有且之前未被选过的点,若对手的点在自己的点的子树内,则该回合自己获胜;若自己的点在对方的点的子树内,该回合自己失败;其他情况视为平局。游戏共进行 \(m\) 回合。
你需要对于 \(k=0,1,2,\cdots,m\),计算出非平局回合数为 \(k\) 的情况数。两种情况不同当且仅当存在一个小 A 拥有的点 \(x\),小 B 在 \(x\) 被小 A 选择的那个回合所选择的点不同。
设
\(f(k)\) 表示至少 \(k\) 对祖孙关系的方案,
\(g(k)\) 表示恰好 \(k\) 对祖孙关系的方案。
显然有:
反演得:
\(f\) 的计算可以使用树形背包,设 \(dp[u][x]\) 表示 \(u\) 子树内至少选择了 \(x\) 对点的方案,从子树内选没有被选过的相反颜色点即可。