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...
CF1228E Another Filling the Grid
CodeforcesLuogu分析显然可以考虑容斥。枚举 $i$ 行 $j$ 列的最小值不为 $1$，可以得到答案为代码// =================================== // author: M_sea // website: http://m-sea-blog.com/ // =================================== #in...
CF839D Winter is here
CodeforcesLuogu分析设 $dp_i$ 表示 $\gcd$ 为 $i$ 的子序列的总长度。考虑容斥，用 $\gcd$ 为 $i$ 的倍数（包括 $i$）的子序列的总长度减去 $\gcd$ 为 $i$ 的倍数（不包括 $i$）的子序列的总长度。先考虑第一部分。设 $s$ 为 $i$ 的倍数的个数，则第一部分的答案为于是就很容易算出 $dp_i$ 了。实现上统计 $i$ 的倍数个数时...
JOI 2018 Final 简要题解
寒冬暖炉同 CF1110B Tape。先令每个客人来的时刻都开暖炉，其它时刻关暖炉。那么每次选最短的一段间隔不关直到只有 $k$ 段即可。代码美术展览显然将所有艺术品按 $A_i$ 排序后答案一定是连续的一段。设 $sum_i$ 表示 $\sum_{j=1}^iB_j$，那么题目给的那个式子可以拆成 $sum_r-sum_{l-1}-A_r+A_l$。因此我们从后往前扫，维护 $sum_i-...
洛谷2567 [SCOI2010]幸运数字
Luogu分析发现自己容斥太菜了，于是来刷几道容斥题。首先预处理出 $[1,b]$ 范围内的所有幸运号码。这个 dfs 一下就行了。考虑到 $[a,b]$ 范围内 $x$ 的倍数个数为然而两个不同的幸运号码的倍数可能是会重复的，于是可以容斥。设 $f(i)$ 为 $[a,b]$ 内 $i$ 个幸运号码的 $\operatorname{lcm}$ 的倍数的个数，那么答案为 $f(1)-f(2)...
洛谷5401 [CTS2019]珍珠
LuoguLOJ分析orz laofu首先题目要求的其实就是方案数。设 $cnt_i$ 表示颜色为 $i$ 的珍珠的数量，那么如果一组方案合法的话会有显然也是一个卷积的形式。于是只需要构造多项式求出 $f_i$ ，再构造多项式求出 $g_i$ ，再求答案即可。另外注意特判 $2m<n-D$ 和 $2m>n$ 的情况，答案分别为 $D^n$ 和 $0$ 。总结：这是一道好题，可是我...