容斥原理

容斥原理吉大附中PoPoQQQ首先来道小学奥数题某校六(1)班假期有45名同学参加了体育训练队，其中参加足球队的有25人，参加排球队的有22人，参加游泳队的有24人，足球、排球都参加的有12人，足球、游泳都参加的有9人，排球、游泳都参加的有8人，问：三项都参加的有多少人？小学奥数？你在逗我！设有x人参加了三项体育训练显然有25+22+24-12-9-8+x=45由Casio定理解得x=3这里我们用到了容斥原理容斥原理：描述成文字就是：n个集合的并集的大小=总和-两两之交+三三之交-四四之交……稍微贴一下度受百科上的证明稍微贴一下度受百科上的证明这证明太吓人了其实仔细看看还是能看懂的治好了我多年的公式恐惧症理论基础铺垫完毕下面进入例题阶段BZOJ2005NOI2010能量采集给定n和m，求考虑当n=m的情况枚举最大公因数p，那么以p为最大公因数的点对的数量等于n/p以内互质的点对的数量而n/p以内互质的点对数=φ(n/p)的前缀和*2-1利用线性筛得到所有数的欧拉函数，这个问题就可以线性出解但是n和m的限制不同，这个方法失效了！考虑容斥原理沿用之前的解法，仍旧枚举最大公因数i令f[i]为以i为最大公因数的点对数这个不是很好求令g[i]为以i为公因数的点对数那么显然有g[i]=(n/i)*(m/i)然而这其中有些数的最大公因数为2i,3i,4i,...我们要把它们减掉考虑容斥原理故有有人可能会有疑问：这不是O(n^2)的么不然对于每个i枚举的次数是O(n/i)O(1/1+1/2+...+1/n)=O(logn)时间复杂度均摊O(nlogn)BZOJ1042硬币购物给定4种硬币的面值，多次询问当这四种硬币有一定数量限制时达到某一价值的方案数每次跑一遍多重背包一定TLE考虑容斥原理首先不考虑限制跑一遍完全背包令f[i]为不考虑限制时达到i价值的方案数然后我们容斥原理BZOJ1042硬币购物最终方案数=不考虑限制的方案数-一种硬币超出限制的方案数+两种硬币超出限制的方案数-三种硬币超出限制的方案数+四种硬币超出限制的方案数如果某种硬币的限制为a[i]，且超出了限制，那么这种硬币至少选择了a[i]+1个方案数即为f[n-(a[i]+1)*w[i]]多个硬币超出限制同理BZOJ3589动态树其实这题和动态树毛关系没有……给定一棵以1为根的有根树，每个节点有点权，提供两种操作：1.以某个节点为根的子树所有节点权值+x2.求一些链的并集的点权和，其中这些链都是由某个节点出发指向链的根BZOJ3589动态树子树修改链上求和，显然树链剖分如果不会链剖可以写线段树维护DFS序看到并集妥妥容斥原理O(2^k)枚举，利用状压确定符号和方案两条链的交集求法如下：令链顶为一条链中深度最小的节点，链底为深度最大的BZOJ3589动态树那么交集的链底为两条链链底的LCA交集的链顶为两条链链顶中深度较大者若交集的链顶深度大于链底则交集为空然后就枚举计算即可链剖时间复杂度O(nlog^2n*2^k)线段树维护DFS序时间复杂度O(nlogn*2^k)挺吓人的但是不会TLE放心写吧这题啥时候变土豪了0.0我写的时候还没呢适用范围1.计数/求和问题2.支持区间加法和区间减法3.本来这题是能做的，但是加了一些令人很容易发表一些感慨的限制，并且限制数非常少(=20)4.反正到最后就是求并集的大小时利用交集的大小来代替广告时间本蒟蒻的Blog