容斥原理
算法简述
在集合S中至少具有,,...中的一个元素的个数是：
主要运用场合及思路：
简单的讲：容斥原理的最重要的应用就是去重。如果完成一件事情有n类方式,...,每一类进行方式有中方法(1 <= i <=n),但是这些方法在合并时存在重叠现象，这时可以选择尝试容斥原理。在比赛中单独使用容斥原理的情况并不多见，常见的问题有错排问题等。
模版
可以用二进制的思想来枚举所有可能的情况，若某位上置1则表示要选取该元素，最后统计1的数目的奇偶性来判断是加上还是减去所求的值。可参考以下结构：
for(int i = 0;i < (1 << fn);i ++){
int cnt = 0;
int num = 1;
for(int j = 0;j < fn;j ++){
if((1 << j) & i){
num = num * fac[j];
cnt ++;
}
}
LL d = R / num;
if(cnt & 1) ans -= 1LL*num * d * (d+1)/2;
else ans += 1LL*num * d * (d+1)/2;
}
例题
hdu1695 GCD
题意：求有多少对(x,y)(1<=x<=b,1<=y<=d)满足。
思路：在很多题目当中都可以找到此题的身影。注意到gcd(x,y)=k,说明x,y都能被k整除，那么,于是本题就可以转化为求在两个区间内寻找有多少对数互质。假设b<=d,我们可以在中枚举数i，对于每一个i，我们只需找到在中与i互质的个数，最后依次相加就可得到结果。
当i<=b/k时可以用欧拉函数求与i互质的个数，当b/k < i <= d/k时，区间中与i互质的个数 = b/k - （区间中与i不互质的个数）。
区间中与i不互质的数则就是i中素因子的倍数，将它们相加则就是答案，但是由于会有重叠部分，比如6既是2的倍数又是3的倍数，此时就可以用容斥原理来求解。
参考代码:
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define N 100005
#define LL long long
LL elur[N];
int num[N];
int p[N][20];
void init(){
elur[1] = 1;
for(int i = 2;i < N;i ++){
if(!elur[i]){
for(int j = i;j < N;j += i){
if(!elur[j])
elur[j] = j;
elur[j] = elur[j] * (i-1) / i;
p[j][num[j]++] = i;
}
}
elur[i] += elur[i-1];
}
}
int get(int b,int h){
int ans = 0;
for(int i = 1;i < (1 << num[b]);i ++){
int cnt = 0,nu = 1;
for(int j = 0;j < num[b];j ++){
if((1 << j) & i){
cnt ++;
nu *= p[b][j];
}
}
if(cnt & 1) ans += h/nu;
else ans -= h/nu;
}
return ans;
}
int main(){
int t,a,b,c,d,k;
init();
scanf("%d",&t);
int ca = 1;
while(t --){
scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);
printf("Case %d: ",ca ++);
if(k == 0){
puts("0");
continue;
}
if(b > d) swap(b,d);
b /= k,d /= k;
LL ans = elur[b];
for(int i = b + 1;i <= d;i ++){
ans += b - get(i,b);
}
printf("%I64d\n",ans);
}
return 0;
}
hdu4675 GCD of Sequence
题意：给定一个序列a:,,...,(1<=，将该序列修改K位后得到一个序列b:,...,求分别有多少种方案使得b序列的最大公约数分别为[1,m];
思路：设表示公约数中含有d的方案数，表示最大公约数为n的方案数，则，的求法可以这么求：假设有a序列中有sum个数是d的倍数，则还有个数不是d倍数，若则表示我们可以把个不是d的倍数的数改为d的倍数，有 种方法，还剩下个数需要修改那些已经是d的倍数的数，所以需要再乘上 ，于是,若：则无法得到一个合法的序列。得到之后,由于包括 ,我们只需减去就是最后的结果。
参考代码如下：
#include <iostream>
#include <string.h>
#include <algorithm>
#include <stdio.h>
using namespace std;
#define LL long long
const int N = 300050;
const int mod = 1000000007;
int num[N];
LL ans[N];
LL quick(LL a,LL b){
LL ans = 1;
while(b){
if(b&1) ans = ans * a % mod;
a = a * a % mod;
b >>= 1;
}
return ans;
}
LL fac[N],inv[N];
LL cal(LL n,LL m){
return (fac[n] * inv[m] % mod ) * inv[n-m] % mod;
}
int main(){
int n,m,k;
fac[0] = 1;
inv[0] = 1;
for(int i = 1;i < N;i ++){
fac[i] = fac[i-1] * i % mod;
inv[i] = quick(fac[i],mod-2);
}
while(~scanf("%d%d%d",&n,&m,&k)){
memset(num,0,sizeof(num));
int nu;
for(int i = 0;i < n;i ++){
scanf("%d",&nu);
num[nu] ++;
}
for(int i = m;i >= 1;i --){
int sum = 0;
for(int j = i;j <= m;j += i)
sum += num[j];
if(n-sum > k){
ans[i] = 0;
continue;
}
ans[i] = (quick(m/i,n-sum) * quick(m/i-1,k-n+sum) % mod) * cal(sum,k-n+sum) % mod;
for(int j = i * 2;j <= m;j += i)
ans[i] = (ans[i] - ans[j] + mod) % mod;
}
printf("%I64d",ans[1]);
for(int i = 2;i <= m;i ++)
printf(" %I64d",ans[i]);
puts("");
}
return 0;
}
hdu4407 Sum
题意：给定一个的一个原始数列，有2种操作。操作1：1 x y p 求区间[x,y]内与p互质的数只和；操作2：2 x c 将第x个数改为c。一共操作m次(1<= m <= 1000)(1<=n<=400000)
思路：注意到m最大只有1000，这是此题的关键，于是对于每一次询问我们可以先求出在原始数列中与p互质的数之和（分解质因数，容斥，与hdu1695类似），最后若区间内数字有修改再处理一下就是答案了。
参考代码：
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <map>
using namespace std;
#define LL long long
const int N = 400005;
int pri[N],pn;
int fac[N],fn;
bool is[N];
void init(){
memset(is,false,sizeof(is));
pn = 0 ;
for(int i = 2;i < N;i ++){
if(!is[i]){
pri[pn ++] = i;
for(int j = i+i;j < N;j += i)
is[j] = true;
}
}
}
void get(int n){
fn = 0;
for(int i = 0;pri[i] <= n / pri[i] && i < pn;i ++){
if(n % pri[i] == 0){
fac[fn ++] = pri[i];
while(n % pri[i] == 0)
n /= pri[i];
}
}
if(n != 1) fac[fn ++] = n;
}
LL solve(int R){
LL ans = 0;
for(int i = 1;i < (1 << fn);i ++){
int cnt = 0;
int num = 1;
for(int j = 0;j < fn;j ++){
if((1 << j) & i){
num = num * fac[j];
cnt ++;
}
}
LL d = R / num;
if(cnt & 1) ans += 1LL*num * d * (d+1)/2;
else ans -= 1LL*num * d * (d+1)/2;
}
return 1LL*R*(R+1)/2 - ans;
}
int gcd(int m,int n){
return n == 0 ? m : gcd(n,m % n) ;
}
map<int,int>ref;
int main(){
int t;
init();
scanf("%d",&t);
while(t --){
int n,m,p;
scanf("%d%d",&n,&m);
ref.clear();
while(m --){
int op;
scanf("%d",&op);
if(op == 1){
int l,r;
scanf("%d%d%d",&l,&r,&p);
if(l > r) swap(l,r);
get(p);
LL ans = solve(r) - solve(l-1);
map<int,int> :: iterator it = ref.begin();
while(it != ref.end()){
int pos = (*it).first;
if(pos <= r && pos >= l){
if(gcd(p,pos) == 1) ans -= pos;
if(gcd(p,(*it).second) == 1) ans += (*it).second;
}
it ++;
}
printf("%I64d\n",ans);
}else {
int x,c;
scanf("%d%d",&x,&c);
ref[x] = c;
}
}
}
return 0;
}
uvalive7040 color
题意：长度为N的序列，有M种颜色，用恰好K种颜色进行染色，且相邻元素颜色不同，求方案数。
思路：首先想到要使相邻元素互不相同则一共有种方案，这是颜色数不多于K的方案数，于是很容易想到将K置换为K-1，则就是颜色不多于K-1的方案数，两者相减，得到最后的结果。不过这是错误的，原因是你不知道从K种颜色中选择了哪K-1种颜色，而且这样算有交集的情况出现。于是很自然想到用容斥原理解决:最后还要再乘上表示从M种颜色中选择K种颜色。
参考代码：
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define LL long long
const LL mod = 1000000007;
#define N 1000000
LL C[N+10],inv[N+10];
void ini(){
inv[1] = 1;
for(int i = 2;i <= N;i ++){
inv[i] = (mod - mod/i) * inv[mod % i] % mod;
}
}
void getc(int n){
C[0] = 1;
for(int i = 1;i <= n;i ++){
C[i] = (C[i-1]%mod * 1LL*(n-i+1)% mod *inv[i] % mod) % mod;
//printf("%d %lld\n",i,C[i]);
}
}
LL quick(LL n,int k){
LL res = 1;
while(k){
if(k & 1) res = res * n % mod;
n = n * n % mod;
k >>= 1;
}
return res;
}
LL solve(int n,int m,int k){
LL ans = 1LL * k * quick(1LL*(k-1),n-1) % mod;
int t = -1;
getc(k);
for(int i = k - 1 ;i >= 2;i --){
ans = ans + (C[i] *i % mod * quick(1LL*(i-1),n-1) * t % mod + mod) % mod;
ans %= mod;
t = -t;
}
for(int i = 1;i <= k;i ++)
C[i] = (C[i-1]%mod * 1LL*(m-i+1)% mod *inv[i] % mod) % mod;
return ans * C[k] % mod;
}
int main(){
int t;
int n,m,k;
ini();
scanf("%d",&t);
int ca = 1;
while(t --){
scanf("%d%d%d",&n,&m,&k);
printf("Case #%d: ",ca ++);
printf("%lld\n",solve(n,m,k));
}
return 0;
}
hdu5072 Coprime
题意：有n个数，从中选择3个元素组成的形式，求有多少对a，b，c满足三者之间两两互质或两两都不互质。
思路：在组合数学中有一个模型叫做同色三角形，对应此题可以这么求：此题的对立情况是在这个三元组中恰有两个元素两两互质或两两不互质（用表示），用总的情况减去就是答案。从n个数当中选择3个数共有种情况， 假设对于每一个元素有个元素与其互质，则有个元素与其不互质，所以。所以此题的答案就是：。 对于与hdu1695类似这里不再叙述。
参考代码：
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
using namespace std;
#define N 100000
bool vis[N+10];
int pri[N+10];
int pnum;
int a[N+10];
void ini()
{
pnum = 0;
memset(vis,false,sizeof(vis));
for(int i = 2; i <= N; i ++)
{
if(!vis[i])
{
pri[pnum++] = i;
for(int j = i+i; j <= N; j += i)
vis[j] = true;
}
}
}
int n;
int fac[50];
int num[N+10];
void div_fac(int tt,int &cnt)
{
for(int j = 0; j < pnum && pri[j] * pri[j] <= tt; j ++)
{
if(tt % pri[j] == 0)
{
fac[cnt++] = pri[j];
while(tt % pri[j] == 0)
{
tt /= pri[j];
}
}
}
if(tt != 1) fac[cnt++] = tt;
}
void solve()
{
for(int i = 1; i <= n; i ++)
{
int cnt = 0;
div_fac(a[i],cnt);
for(int j = 1; j < (1<<cnt); j ++)
{
int temp = 1;
for(int k = 0; k < cnt; k ++)
if((1<<k) & j)
temp *= fac[k];
num[temp] ++;
}
}
}
long long get()
{
long long ans = 0;
for(int i = 1; i <= n; i ++)
{
int cnt = 0;
div_fac(a[i],cnt);
long long res = 0;
for(int j = 1; j < (1<<cnt); j ++)
{
int temp = 1;
int Time = 0;
for(int k = 0; k < cnt; k ++)
{
if((1<<k) & j)
{
temp *= fac[k];
Time ++;
}
}
if(Time & 1) res += num[temp];
else res -= num[temp];
}
if(res == 0) continue;
ans += (res - 1)*(n - res);
}
return ans;
}
int main()
{
int t;
ini();
//freopen("a.txt","r",stdin);
scanf("%d",&t);
while(t --)
{
scanf("%d",&n);
for(int i = 1; i <= n; i ++)
{
scanf("%d",&a[i]);
}
memset(num,0,sizeof(num));
solve();
long long ans = 1LL*n*(n-1)*(n-2)/6;
printf("%lld\n",ans - get()/2);
}
return 0;
}