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...
洛谷5400 [CTS2019]随机立方体
LuoguLOJ分析为了方便，设 $n<m<l$，$V=nml$。考虑容斥，求出至少有 $i$ 个极大数的方案数 $c_i$。那么 $c_i$ 等于选出 $i$ 个极大数的方案数、$i$ 个极大数所在的平面的并填数的方案数、其它位置填数的方案数之积。首先考虑求选出 $i$ 个数的方案数 $f_i$，不难得到总时间复杂度 $\mathcal{O}(n)$。代码// ========...
洛谷3270 [JLOI2016]成绩比较
LuoguLOJ分析考虑容斥，求出至少 $i$ 个人被 D 神碾压的方案数 $f_i$。首先钦定 $i$ 个人被 D 神碾压，然后对于每一科选出没有被 D 神碾压但是这一科分数比他低的 $n-r_i-i$ 个人，然后再枚举 D 神的分数并计算出其它人分数的方案数，即可求出 $f_i$，即总时间复杂度为 $\mathcal{O}(n^2m)$。代码// ====================...
CF708E Student's Camp
CodeforcesLuogu分析显然营地不连通只能是上下分开，即存在相邻两行剩下的砖块区间没有交。考虑 DP。设 $f_{i,j,k}$ 表示前 $i$ 行，第 $i$ 行剩下 $[j,k]$，且前 $i$ 行连通的概率。容易得到转移于是只要求出 $d_{l-1}$ 和 $d_{l-1}sr_{i-1,l-1}$ 的前缀和即可。第一个可以提前预处理出，第二个可以在 DP 时维护。边界为 $...
洛谷5405 [CTS2019]氪金手游
LuoguLOJ分析首先考虑原树为外向树的情况。此时 $u$ 子树中所有点选择时间都应比 $u$ 晚。考虑这个概率。设 $u$ 子树 $w_i$ 的和为 $s$，整棵树 $w_i$ 的和为 $S$，则 $u$ 子树中所有点选择时间都比 $u$ 晚的概率为这个概率只和子树有关，因此可以设 $dp_{i,j}$ 表示以 $i$ 为根的子树 $w_i$ 和为 $j$ 的概率，转移即为树形背包。现在...
51nod1805 小树
51nod分析考虑一棵满足条件的树的 prufer 序列，可以发现有恰好 $m$ 个数没有出现过。考虑容斥，则我们需要求出至少 $i$ 个数没有出现的方案数，即为代码// =================================== // author: M_sea // website: http://m-sea-blog.com/ // ================...
51nod1667 概率好题
51nod分析甲胜和乙胜类似，三者概率之和为 $1$，因此只考虑计算甲胜的概率，即甲胜的方案数除以总方案数。设甲的第 $i$ 个数为 $X_i$，乙的第 $i$ 个数为 $Y_i$，则甲胜当且仅当则我们相当于要求这个 $k_1+k_2+1$ 元不定方程的非负解数，其中一些变量有上界。考虑容斥掉上界的限制，即钦定一些变量超过了上界，则我们只需要计算不定方程 $\sum_{i=1}^n x_i=...
洛谷6076 [JSOI2015]染色问题
Luogu分析考虑容斥。枚举 $i$ 行 $j$ 列不填、$k$ 种颜色不用。不难得到答案为代码// =================================== // author: M_sea // website: http://m-sea-blog.com/ // =================================== #include <bi...
AtCoder Grand Contest 005 简要题解
比赛地址STring和括号匹配是类似的，开一个栈记一下就好了。事实上只要记栈中的元素个数。代码Minimum Sum单调栈板子题。代码Tree Restoring首先找到 $d=\max\left\{a_i\right\}$，那么直径的长度为 $d$。设 $cnt_i$ 表示满足 $a_j=i$ 的 $j$ 的数量，分类讨论一下：若 $d$ 为奇数，则应有 考虑计算 $f_i$。容易发现一...