标签 容斥 下的文章
- 首页
- 容斥
Comet OJ Contest #2 D 错综的光影所迷惑的思念是
Comet OJ分析可以发现一个点集的所有直径的中点都相同。为了方便我们把边也拆成点，这样子中点一定是一个点。枚举中点和半径，那么深度小于半径的点任意选，深度等于半径的必须有至少两棵子树中选了，容斥一下即可。代码// ==================================== // author: M_sea // website: https://m-sea-blog...
JOISC2018 部分题解
高速道路の建設 / Construction of Highway这个操作长得很像 LCT 中的 access。于是我们每次只要 access 一下并把所有颜色段拿出来，然后树状数组求逆序对数，再把对应的边连上并把整条重链的颜色赋值为 $c_v$。因为 access 是均摊 $\mathcal{O}(\log n)$ 的，所以每次颜色段数也是均摊 $\mathcal{O}(\log n)$ ...
洛谷6295 有标号 DAG 计数
Luogu分析设 $f_i$ 为 $i$ 个点的 DAG 数量。一个想法是枚举入度为 $0$ 的点的数量，有多项式求逆即可。现在还要求弱连通，那么把 $F(x)$ 求个多项式 $\ln$ 即可。代码// ==================================== // author: M_sea // website: https://m-sea-blog.com/ /...
AtCoder Regular Contest 064 简要题解
比赛地址Boxes and Candies从左往右扫一遍，尽量先拿走靠右的即可。正确性显然。代码An Ordinary Game这个 D 怎么比 E 难啊设 $s$ 为原串，$n$ 为串长。给出结论：当 $s_1=s_n$ 时，如果 $n$ 为奇数则后手必胜，否则先手必胜；当 $s_1\neq s_n$ 时，如果 $n$ 为奇数则先手必胜，否则后手必胜。先证明 $s_1=s_n$ 时的情况。...
洛谷4491 [HAOI2018]染色
LuoguLOJ分析显然一块画布上出现次数为 $S$ 的颜色不超过 $L=\min\left\{m,\left\lfloor\frac{n}{S}\right\rfloor\right\}$ 种。考虑容斥。设 $f_i$ 为出现次数为 $S$ 的颜色有至少 $i$ 种的方案数，不难得到可以发现是一个差卷积的形式，于是直接 NTT 即可。代码// =======================...
CF917D Stranger Trees
CodeforcesLuogu算法一分析设树边的权值为 $x$，非树边的权值为 $1$，然后矩阵树定理。设得到的多项式为 $F(x)$，那么显然 $k=i$ 时的答案即为 $[x^i]F(x)$。然而直接 MTT + 高斯消元显然是过不去的。但是 $F(x)$ 是一个 $n-1$ 次多项式，所以我们可以把 $x=[1,n]$ 代进去求出 $F(1..n)$，然后解方程组解出系数即可。时间复杂...
CF1093F Vasya and Array
CodeforcesLuogu分析设 $dp_{i,j}$ 表示前 $i$ 个数，第 $i$ 位填 $j$ 的方案数，$s_i$ 表示 $\sum_{j=1}^k dp_{i,j}$，$len_{i,j}$ 表示第 $i$ 位往前最多有多少位为 $j$。转移时讨论一下。当 $len_{i,j}<l$ 时 $dp_{i,j}=s_{i-1}$；否则要减去超长的那一部分，即为 $dp_{i...
LOJ6503 「雅礼集训 2018 Day4」Magic
LOJ分析容易想到容斥，计算至少包含 $i$ 个魔术对的序列数 $g_i$。根据二项式反演不难得到分治求出所有 $f_i$ 的卷积即可得到 $dp_m$。然而 $dp_{m,i}$ 并不等于 $g_i$，因为我们还可以任意排列不构成魔术对的 $n-i$ 张牌，所以还需要乘上一个 $(n-i)!$。最后二项式反演一下即可得到答案。记得把答案除掉 $\prod a_i!$。代码// ======...
LOJ575 「LibreOJ NOI Round #2」不等关系
LOJ分析假设 > 是没有限制的，那么整个序列被 < 划分为若干段。设这些段的长度为 $a_1,a_2,\cdots$，则方案数为边界为 $dp_0=0$。将 $(-1)^{cnt_{i-1}}$ 提出后分治 NTT 即可。代码// =================================== // author: M_sea // website: https...