思路
今天时间剩的不多, 还是看看得了
发现听过某个巨佬讲这道题, 可惜忘了
你发现约束条件数 \(m\) 很小啊, 容易想到状压, 但这是后事了
先考虑一下有没有什么符合直觉的做法, 你发现他求 \(n\) 个元素的子集? 这我写鸡毛啊
算了反正状态不好, 复习一下回寝了
下一次写这个题还要等到考完试补完题, 很蓝的啦
考完复活了
简化题意
有 \(n\) 个人和 \(m\) 对敌对关系, 每一个人有一个条件区间 \([l_i,r_i]\)
现在要在这 \(n\) 个人中选 若干个人 , 定义一个合法的选择 \(\{S\}\) , 当且仅当对于 \(\{S\}\) 中的所有人 \(i\) , \(l_i\le \lvert S \rvert \le r_i\), 且 \(\{S\}\) 中所有人互不敌对
求有多少种合法的选择
因为求 \(n \leq 3 \times 10^5\) 这个的所有子集显然不可能, 考虑有没有什么好的性质可以避开
先考虑互不敌对这个条件, 你发现因为敌对数很少啊, 所以互不敌对的子集其实是很多的, 我们考虑正难则反, 考虑敌对子集
这个是简单的, 我们可以记录满足了哪些敌对状态, 仅仅只有 \(2^{20} - 1\) 个状态
知道了满足了那些敌对状态, 那么就知道必须要有哪些人出现, 然后其他人任选
好那么进入正题, 你发现给定「满足敌对状态」, 我们只能「钦定」这些人出现, 也就是说我们只能找到「至少」出现了 \(k\) 个敌对状态的方案数, 套路的, 记为 \(f(k)\)
然后你套路的令 \(g(k)\) 为「恰好」出现了 \(k\) 个敌对状态的方案数, 然后就计算出来了
需要证明的是, 二项式反演能否在这里使用
我们都知道这个柿子
\[f(k) = \sum_{i = k}^{n} {i \choose k} g(i) \iff g(k) = \sum_{i = k}^{n} (-1)^{i - k} {i \choose k} f(i) \]容易发现的是在这种情况下, \(f(k)\) 的表达式仍然正确, 所以仍然可以这样反演
那么
\[ans = g(0) = \sum_{i = 0}^{n} (-1)^i f(i) \]说个大家不爱听的, 容斥真王朝了
但是你发现什么呢, 我们之前没有考虑 条件区间 这个东西, 但是这个肯定是要加入讨论的, 也就是说, 求 \(f(k)\) 的方法还需要讨论
首先确定 \(f(k)\) 的意义是什么 : \(f(k)\) 表示「钦定」\(k\) 个敌对关系必须成立的满足条件区间的子集方案数
容易发现的是, 对于敌对关系的状态 \(\mathbb{S}\) , 我们可以「钦定」出那些人必须在选择集合之中, 如果这些人之间不满足条件区间, 那么一定不成立, 否则考虑向外填其他不在敌对关系之中的人, 但是如何确定满足条件区间的要求?
首先我们记敌对关系产生的子集为 \(\mathbb{U}\) , 那么先找到 \(\mathbb{U}\) 中
\(\displaystyle L = \max_{i \in \mathbb{U}} l_i\) 和 \(\displaystyle R = \min_{i \in \mathbb{U}} r_i\) , 最终的子集大小一定要在 \([L, R]\) 之间
我们考虑当前的约束条件有那些 (假设加入的人的点集为 \(\mathbb{P}\) , 其中 \(\mathbb{P} \cap \mathbb{U} = \varnothing\)):
- \(L \leq \lvert \mathbb{U} \rvert + \lvert \mathbb{P} \rvert \leq R\)
- $\forall i \in \mathbb{P}, l_i \leq \lvert \mathbb{U} \rvert + \lvert \mathbb{P} \rvert \leq r_i $
不好处理的是第二个限制, 我们考虑预处理
可以预处理出最终选点个数一定时(即确定 \(\lvert \mathbb{U} \rvert + \lvert \mathbb{P} \rvert\)) , 可能的选点方案数
你容易发现, 满足 \(l_i \leq x \leq r_i\) 的数的个数是一定的, 我们记为 \(t_x\)
这样我们可以计算 \(f(k)\)
实现
为了检验思路的正确性, 还是要自己写代码, 后补
总结
正难则反, 转化成「钦定」类问题
「钦定」类问题往往要向「二项式反演」转化
约束条件不好处理的时候, 全部列出来冷静分析
预处理可以方便的解决一些问题
直接用组合数不好解决的问题, 你考虑枚举一些信息方便组合数的计算, 常见的是枚举最终选了多少个