Phecda_

分类

未归档(109)

/ 注册

全部文章（共4篇）

2019.08.25校内模拟赛Graph

其实这是道很难的容斥. 所以我考场上直接考虑了\(m=0\)的暴力和白给的\(m=\cfrac{n(n-1)}{2}\)的\(10\)分. 白给的那十分是完全图,根据题意就只需要输出\(0\)就行了. 而至于\(m=0\)的\(40pts\),稍加思索就会发现它和错排是双射关系... 于是,就直接错...

数论错排组合计数容斥原理

2019-08-25

0 389

ZROI#999

ZROI#999 很有趣的一道题.本来我是想考虑枚举选几个盒子,但我发现这样并没有对问题有任何简化. 然后就考虑容斥嘛...发现,这个容斥比较简单. 假如令\(f(S)\)为\(S\)集合中的玩具不能选的方案数. 那么答案就是: \[\sum_{s\subseteq T}{(-1)^{|S|}f(S...

容斥原理子集容斥 FMT(高维前缀和)

2019-09-08

0 288

ZROI#987

ZROI#987 差分+简单数学即可. 首先有个性质: 两条链相交等价于其中一条链的\(LCA\)在另一条链上. 于是我们就对每一条链的\(LCA\)都加\(1\). 最后查询每一条链的区间和即可.树剖实现. 但这样我们会算重复,就是说\((a,b)\)两条链相交我们会算\((a,b)\)一次,\...

nature 差分树链剖分线段树容斥原理

2019-09-15

0 495

ZROI#985

ZROI#985 暴力就不说了,说说正解吧. 先假定每个区间都没有重复元素,然后得到一个全集的答案. 然后我们考虑,减掉不合法的方案. 记录每种颜色出现的位置,乘法原理即可. 暴力\(Code:\) #include <iostream> #include <cstdlib&g...

容斥原理组合计数

2019-09-15

0 367