洛谷6295 有标号 DAG 计数
Luogu 分析 设 $f_i$ 为 $i$ 个点的 DAG 数量。 一个想法是枚举入度为 $0$ 的点的数量，有 多项式求逆即可。 现在还要求弱连通，那么把 $F(x)$ 求个多项式 $\ln$ 即可。 代码 // ==================================== // author: M_sea // website: https://m-sea-blo...
标签 容斥 下的文章
- 首页
- 容斥
洛谷4491 [HAOI2018]染色
Luogu LOJ 分析 显然一块画布上出现次数为 $S$ 的颜色不超过 $L=\min\left\{m,\left\lfloor\frac{n}{S}\right\rfloor\right\}$ 种。 考虑容斥。设 $f_i$ 为出现次数为 $S$ 的颜色有至少 $i$ 种的方案数，不难得到 可以发现是一个差卷积的形式，于是直接 NTT 即可。 代码 // ===============...
CF917D Stranger Trees
Codeforces Luogu 算法一 分析 设树边的权值为 $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
Codeforces Luogu 分析 设 $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}$；否则要减去超长的那一部分，即为 $d...
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:...
洛谷5400 [CTS2019]随机立方体
Luogu LOJ 分析 为了方便，设 $n<m<l$，$V=nml$。 考虑容斥，求出至少有 $i$ 个极大数的方案数 $c_i$。 那么 $c_i$ 等于选出 $i$ 个极大数的方案数、$i$ 个极大数所在的平面的并填数的方案数、其它位置填数的方案数之积。 首先考虑求选出 $i$ 个数的方案数 $f_i$，不难得到 总时间复杂度 $\mathcal{O}(n)$。 代码 /...
洛谷3270 [JLOI2016]成绩比较
Luogu LOJ 分析 考虑容斥，求出至少 $i$ 个人被 D 神碾压的方案数 $f_i$。 首先钦定 $i$ 个人被 D 神碾压，然后对于每一科选出没有被 D 神碾压但是这一科分数比他低的 $n-r_i-i$ 个人，然后再枚举 D 神的分数并计算出其它人分数的方案数，即可求出 $f_i$，即 总时间复杂度为 $\mathcal{O}(n^2m)$。 代码 // ============...
CF708E Student's Camp
Codeforces Luogu 分析 显然营地不连通只能是上下分开，即存在相邻两行剩下的砖块区间没有交。 考虑 DP。设 $f_{i,j,k}$ 表示前 $i$ 行，第 $i$ 行剩下 $[j,k]$，且前 $i$ 行连通的概率。容易得到转移 于是只要求出 $d_{l-1}$ 和 $d_{l-1}sr_{i-1,l-1}$ 的前缀和即可。第一个可以提前预处理出，第二个可以在 DP 时维护...
洛谷5405 [CTS2019]氪金手游
Luogu LOJ 分析 首先考虑原树为外向树的情况。此时 $u$ 子树中所有点选择时间都应比 $u$ 晚。 考虑这个概率。设 $u$ 子树 $w_i$ 的和为 $s$，整棵树 $w_i$ 的和为 $S$，则 $u$ 子树中所有点选择时间都比 $u$ 晚的概率为 这个概率只和子树有关，因此可以设 $dp_{i,j}$ 表示以 $i$ 为根的子树 $w_i$ 和为 $j$ 的概率，转移即为树...