容斥专题
hdu4407(容斥原理)
题意：给一串数字1,2，......n，两个操作:1、修改第k个数字，2、查询区间[l,r]中与n互质的数之和。 解题思路：咱一看，像线段树，但是如果用线段树做，那么每个区间一定要记录所有的素因子，这样会超内存。然后我就做不来了。后来看了题解，原来是用容斥原理来做的。还记得这道题目吗？求区间[1,r]中与p互质的数的个数，如果不会的话就先去做那题吧。现在这题是求区间[l,r]中与n互质的数的和
hdu4407容斥原理
题意： 有一个元素为 1~n 的数列{An}，有2种操作（1000次）： 1、求某段区间 [a,b] 中与 p 互质的数的和。 2、将数列中某个位置元素的值改变。 import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOException;import java.io.Inpu
hdu4059容斥原理
求1-n中与n互质的数的4次方之和 import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream;import java.io.InputStreamReader;import java.io.PrintWrit
【HDU】2204 Eddy's爱好 容斥原理
传送门：【HDU】2204 Eddy's爱好 题目分析：首先，对于所有形如M^K的数我们都可以转化成M^(p1^k1 * p2^k2 * p3^k3 * ... )的形式，其中p1,p2,p3..为素数。则所有的M^K都可以转化成M'^p，其中p为素数。我们意识到2^60>10^18，所以只要求出前60以内的所有素数即可。然后，由于2*3*5*7>60，其中一个K的质因数最多只有三种。
【ZOJ】3881 From the ABC conjecture【暴力容斥】
传送门：【ZOJ】3881 From the ABC conjecture 复杂度大概 O(N0.67) O(N^{0.67})，我也不会算www，首先转换一下（我们是根据积性函数打表找规律得到的，也可以推出来）使得： g(N)=∏pi ϵ N(pia+1) g(N)=\prod_{pi~\epsilon ~N} (pi^a+1) 暴力展开发现贡献为： h(N)=
HDU 5514 Frogs （容斥定理）
题意：有n个青蛙在由m个石头组成的圆圈上跳。告诉你每个青蛙每次跳的步长，计算所有被青蛙跳过的石头的编号和。 解法：http://www.cnblogs.com/qscqesze/p/4933949.html #include<bits/stdc++.h>using namespace std;#define LL long long#define pb push_back#defin
poj 1091 跳蚤（不定方程+容斥）
跳蚤 Time Limit: 1000MS Memory Limit: 10000KTotal Submissions: 8731 Accepted: 2605 Description Z城市居住着很多只跳蚤。在Z城市周六生活频道有一个娱乐节目。一只跳蚤将被请上一个高空钢丝的正中央。钢丝很长，可以看作是无限长。节目主持人会给该跳蚤发一张卡片。卡片上写有N+1个自然数。其中最
POJ 3904 Sky Code 容斥原理
题目来源：POJ 3904 Sky Code 题意：选出最大公约数为1的四元组的方案 思路：容斥原理 总的方案C(n,4)减去t(1)+t(2)-t(3)+...+(-)^kt(k) t(i)表示四元组质因子的个数为i的方案数 #include <cstdio>#include <cstring>#include <algorithm>using namespace std;con
HDU 1695 GCD 容斥原理/莫比乌斯反演
题意： 给你两个区间[a,b],[c,d]，还有一个k。让你从区间[a,b]中找出x，[c,d]中找出y，问共有多少组（x，y）使得gcd（x，y）=k。 （x，y）和（y，x）算一组。 思路： 参考：http://blog.csdn.net/yang_7_46/article/details/9072533 容斥。 普通容斥： *如果gcd（x，y）=k，则gcd（x/k
HDU 2841 Visible Trees 容斥
题意（一开始也没怎么看懂）： 一个人站在（0，0）处，树从（1，1）点开始排，共有m*n棵。如果两棵树在同一视线上（意思是两个点和（0，0）的斜率相同），则只看到前面一棵树，问你那个人能看到几棵树。 思路： 容斥。 简单分析之后，其实本质就是让你求gcd(x,y)=1有几组。（x，y）和（y，x）算两种。 这题和HDU 1695差不多，只不过那题（x，y）和（y，x）算一种。
ZOJ 2836 Number Puzzle 容斥、lcm
这题和HDU 1796差不多。 code： #include <cstring>#include <iostream>#include <cstdlib>#include <cstdio>#include <vector>#include <algorithm>using namespace std;typedef long long LL;const int MAXN =
HDU 1796 How many integers can you find 容斥、lcm
题意： 输入n和m个数。问你小于n中，有几个数能够被m个数中的任意一个整除的。 思路： 容斥+lcm（最小公倍数） 设m数组中结果为｛a1，a2，a3，……，am｝; 1.加上n/a1，n/a2，n/a3……的个数。 2.减去n/lcm(a1,a2)，n/lcm(a1*a3)，……，n/lcm(a2*a3)，n/lcm(a2*a4),……； 3.加上三个集合的，然后减去四个集合的，加
HDU 3208 Integer’s Power 指数和、容斥
题意： 输入l，r，求出[l, r]区间内，表示成指数形式的指数和。 要求a^b，a尽量小，b尽量大。例如，16应该表示成2^4，而不是4^2。 思路： 参考自：http://blog.csdn.net/acdreamers/article/details/10977785 这算是容斥吧？初学的我也不大懂。 如果我们可以知道每个指数所表示的个数，那么问题就可以解决了。 感觉像
HDU 2204 Eddy's爱好 容斥
题意： 输入n，求出1~n中，有多少个值可以表示为M^K（K>1）。 思路： 容斥。这题算是我的容斥第一题吧。现在回头看容斥原理，就是奇数个集合就加，偶数个集合就减（说得貌似顶简单，在做题过程中找该容斥什么也蛮累的= =）。 首先看这个，对于2^4和4^2，如果直接计算个数，这样会导致重复。因此指数应该强制为质数（素数），则可以避免这个问题（根据算术基本定理，一个大于1的值总能表示为素数的
组队赛4解题报告（组合数学+禁位排列+容斥原理+精度进位+贪心背包+矩阵快速幂）
B题：ZOJ 3687 链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4970 题意：在d天看不了c章，问复习的方案有多少种？ 思路：这题比赛的时候看出是组合数组和容斥原理了，不过不会做，所以一直托到现在了才做。而且自己又看别人的解题报告理解了一下午才理解明白……笨了…… 我在百度文库上已经知道错排和禁位排列是什
uva 11123 - Counting Trapizoid(容斥+几何)
题目链接：uva 11123 - Counting Trapizoid 题目大意：给定若干个点，问有多少种梯形，不包括矩形，梯形的面积必须为正数。因为是点的集合，所以不会优重复的点。 解题思路：枚举两两点，求出该条直线，包括斜率k，偏移值c，以及长度l。已知梯形的性质，一对对边平行，也就是说一对平行但是不相等的边。 所以将所有线段按照斜率排序，假设对于某一斜率，有m条边，那么这m条边
UVA 10458 - Cricket Ranking(容斥原理)
UVA 10458 - Cricket Ranking 题目链接 题意：给定k个区间，要求用这些数字范围去组合成n，问有几种组合方式 思路：容斥原理，容斥是这样做：已知n个组成s，不限值个数的话，用隔板法求出情况为C(s + n - 1, n - 1)，但是这部分包含了超过了，那么就利用二进制枚举出哪些是超过的，实现把s减去f(i) + 1这样就保证这个位置是超过的，减去这部分后，有
UVA 10542 - Hyper-drive（容斥原理）
UVA 10542 - Hyper-drive 题目链接 题意：给定一些个d维的方块，给定两点，求穿过多少方块 思路：容斥原理，每次选出一些维度，如果gcd(a, b)，就会穿过多少点，对应的就减少穿过多少方块，所以最后得到式子d1 + d2 + .. dn - gcd(d1, d2)..+gcd(d1, d2, d3)... 代码： #include <cstdio>
HDU 3929 Big Coefficients（容斥+证明）
(1 + x)^n 的奇数项系数个数等于 2^(bitcount(n))，bitcount(x)为x有多少个1. 然后容斥 枚举每一项存在不存在，然后容斥加加减减即可 这题用二进制枚举会T，只能DFS 代码： #include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int
ZOJ 3556 How Many Sets I （容斥）
这题是个容斥。 总情况有2^(nk)中，但是其中包含了1个重复元素，2个，3个。。 用容斥，1个重复元素加上，2个减去，3个加上 这样推出公式为 C(n, 0)2^(nk) - C(n, 1)2^((n -1)k) + C(n, 2)2^((n - 2)k)...... ==> (2^k - 1)^n 快速幂取模计算即可 代码： #include <cstdio>#incl
CF451E: Devu and Flowers（容斥原理 + 考虑反面 + golang组合模版）
题目截图 题目翻译 题目分析 正难则反，考虑所有不符合的例子 由于n很小，所以可以状态压缩二进制遍历完全部不符合例子的组合 对于不符合的例子，假设其中第i个不符合，那么就消耗掉fi + 1个球 以此类推，减剩下s2个球 这时候使用隔板法分给n个箱子，加上n - 1个挡板，就是comb(s2 + n - 1, n - 1) 对于容斥原理，奇偶个数要对应不同的符号，这里需要注意 go代
第四届上海理工大学程序设计全国挑战赛 J.上学 题解 DFS 容斥
上学 题目描述 usst 小学里有 n 名学生，他们分别居住在 n 个地点，第 i 名学生居住在第 i 个地点，这些地点由 n−1 条双向道路连接，保证任意两个地点之间可以通过若干条双向道路抵达。学校则位于另外的第 0 个地点，第 0 个地点与第 1 个地点之间有另外一条双向道路链接。 最近学校开始启用校车来接学生上学，每一辆校车上都可以坐无限个学生，且每辆校车在一天内不会重复经过一条道路，
24.4.28（板刷dp,拓扑判环,区间dp+容斥算回文串总数）
星期一： 昨晚cf又掉分，小掉不算掉 补ABC350 D atc传送门 思路：对每个连通块，使其成为一个完全图，完全图的边数为 n*(n-1)/2 , 答案加上每个连通块成为完全图后的边数，最后再减去m即可 代码如下（dfs实现： const int N=2e6+10,M=210;c