CF383E Vowels
Codeforces 分析 这个数量平方的异或和感觉没有什么性质，那么我们只能想办法对每个集合求出数量。 一个想法是先预处理出集合大小为 $1$ 时的数量，然后做子集和，但是这样子会算重：对于 $abc$，$ab$ 处将其计算了两次。 于是考虑容斥：我们在 $a, b, c$ 处加 $1$，$ab, ac, bc$ 处减 $1$、$abc$ 处加 $1$，那么这样子做子集和求出来的数量就是正...
标签 容斥 下的文章
- 首页
- 容斥
洛谷3214 [HNOI2011]卡农
Luogu 分析 首先题目中的集合是无序的，我们将其转为有序的来计算，只需要最后除以 $m!$ 即可。 设 $f_i$ 表示划分为 $i$ 个片段的方案数，考虑转移。 首先，如果我们已经确定了前 $i - 1$ 个片段，那么第 $i$ 个片段唯一确定，这样子的方案数为 $A_{2^n - 1}^{i - 1}$。 但是这样子会有一些不合法的情况： 第 $i$ 个片段为空：这样子去掉第 $i...
LOJ3399 「2020-2021 集训队作业」Communication Network
LOJ 分析 感觉和 WC2019 数树 的 $op = 1$ 基本一致，如果不会可以戳 这里。 我们还是套用 $\displaystyle |S| \prod_{i = 1}^k na_i$ 有着清晰的组合意义：从 $S$ 中选择一条边，再从每个连通块中选择一个点，每个点产生 $n$ 的乘积贡献。我们要求所有 $S$ 的贡献的总和。 考虑 DP。设 $f_{u, 0/1, 0/1}$ ...
洛谷5206 [WC2019]数树
Luogu LOJ orz laofu！!1 分析 $op = 0$ 只需要统计两棵树有多少条重边即可。假设有 $c$ 条，答案即为 $y^{n - c}$。 $op = 1$ 先特判掉 $y = 1$ 的情况，答案为 $n^{n - 2}$。 我们要求的是 考察每个连通分量。一个大小为 $a$ 的连通分量会产生 $\frac{n^2 y}{1 - y} a^2$ 的乘积贡献，而 $a$...
LOJ6358 前夕
LOJ 分析 考虑求出交集大小至少为 $k$ 的方案数 $f(k)$，显然有 从小到大枚举 $k$，动态维护 $(\omega ^ j - 1) ^ k$ 即可 $\mathcal{O}(n)$ 计算。 代码 // ==================================== // author: M_sea // website: https://m-sea-blog...
AGC036F Square Constraints
AtCoder Luogu 分析 题目相当于限定只能放在两个圆中间，求放 $2n$ 个车的方案数。 事实上我们可以对每一列求出其能放置车的范围 $[L_i, R_i]$。可以发现，对于所有 $i\in[n, 2n)$，都有 $L_i = 0$。 如果所有 $L_i$ 都为 $0$，这就是一个经典问题：将 $R_i$ 从小到大排序，答案即为 $\prod_{i = 0}^{2n - 1} (R...
洛谷5339 [TJOI2019]唱、跳、rap 和篮球
Luogu LOJ 分析 考虑容斥，问题变为计算至少有 $i$ 组人讨论 cxk 的方案数。 首先我们需要选出 $i$ 个位置 $p_{1..i}$ 满足 $[p_j,p_j+3]$ 不交，容易算出方案数为 ${n-3i\choose i}$。 对于剩下的位置，枚举每种学生的个数，方案数是一个多重集排列数，式子是 可以看成四个生成函数卷起来，用 NTT 可以 $\mathcal{O}(n\...
Comet OJ Contest #2 D 错综的光影所迷惑的思念是
Comet OJ 分析 可以发现一个点集的所有直径的中点都相同。为了方便我们把边也拆成点，这样子中点一定是一个点。 枚举中点和半径，那么深度小于半径的点任意选，深度等于半径的必须有至少两棵子树中选了，容斥一下即可。 代码 // ==================================== // author: M_sea // website: https://m-sea...
JOISC2018 部分题解
高速道路の建設 / Construction of Highway 这个操作长得很像 LCT 中的 access。 于是我们每次只要 access 一下并把所有颜色段拿出来，然后树状数组求逆序对数，再把对应的边连上并把整条重链的颜色赋值为 $c_v$。 因为 access 是均摊 $\mathcal{O}(\log n)$ 的，所以每次颜色段数也是均摊 $\mathcal{O}(\log n...