题目链接 题意：求曼哈顿距离和平方根距离相等的点的对数？ 思路：化简发现是绝对值乘积等于0，容斥搞搞。 /* *********************************************** Author :111qqz Created Time :2016年03月07日 星期一 18时43分02秒 File Name :code/C.cpp ************************************************ */ #include <cstdio> #include <cstring> #include <iostream> #include …

题意：F(x) = (1+x)^a1 + (1+x)^a2 + … + (1+x)^am，求系数是奇数的项的个数。 思路：解题报告 涉及到的由lucas定理得到的推论的证明lucas定理证明 以及这篇理解里有递归形式的容斥定理的一般写法。。递归形式的容斥定理 dfs(int beg,set S,int sym) { ans+=num(S)*sym; for(int i=beg;i<=n;i++) dfs(i,S∩A[i],sym*-1); } for(int i=1;i<=n;i++) dfs(i,A[i],1); 第一次接触递归形式的容斥定理...还不是特别理解，据说要比循环的写法少一层msk(应该是少一 …

hdu1796 题意：给出n（<=2^31）以及m(<=10)个元素组成的无重复元素集合，集合元素0<=a[i]<=20,问有多少个小于n的数能至少被集合中的一个元素整除。 思路：容斥，找到能被一个元素的，被两个元素的...加加减减。 一个元素的最小公倍数定义成自己，然后多个元素的就两个两个算... 一个坑点是，a[i]有0，而一个数除以0没有意义。。。所以读入的时候处理下。。。把0删掉（个人觉得这个坑点毫无技术含量。。。。0不能作为除数这种事情呵呵呵） 并且如果只有一个数且为0，那么删掉后集合就为空了，特判输出0. 另一个坑点是，别看每个数都很小。。但是求多个数的最小公倍数的时候会爆int... **虽然最 …

http://acm.hdu.edu.cn/showproblem.php?pid=4336 题意：有n种卡片，买一包干脆面得到第i种卡片的概率是p[i],每包干脆面最多有一张卡片，问收集齐所有卡片要买的干脆面的包数的数学期望。 思路：容斥模板题。1.0/p[i]就是拿到某张卡片需要买的包数的数学期望 注意体会这种具体应用容斥的模拟方法，把1<<n转化成二进制来模拟有1个元素的集合，有2个元素的集合...有n个元素的集合。 核心代码： for ( int msk = 1 ; msk <(1<<n) ; msk++) { double res = 0.0; int bits = 0; for ( int …

http://acm.hdu.edu.cn/showproblem.php?pid=5213 题意：n个数，m个查询，每个查询由4个数l1,r1,l2,r2构成，询问分别从[l1,r1]和[l2,r2]中各取一个数，和为给定的常数k的方案数。 思路：首先分别由两个区间取数不好搞，我们可以用容斥原理对区间变换。这是这道题最关键的一步。 官方题解：这道题需要一些莫队算法的知识 定义记号f(A,B)f(A,B)表示询问区间A，B时的答案 用记号＋表示集合的并 利用莫队算法我们可以计算出任意f(A,A)f(A,A)的值 不妨假 …