容斥原理是一个从小学就开始学习的算法。但是很多难题现在都觉得做的十分吃力。
容斥原理大概有两种表现形式，一种是按照倍数进行容斥，这个东西直接用莫比乌斯函数就可以了。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAXN 200100
typedef long long qword;
bool pflag[MAXN];
int prime[MAXN],topp=-;
int mu[MAXN];
int a[MAXN],tota;
int b[MAXN],totb;
void init()
{
for (register int i=;i<MAXN;i++)
{
if (!pflag[i])
{
prime[++topp]=i;
mu[i]=;
}
for (register int j=;j<=topp && i*prime[j]<MAXN;j++)
{
pflag[i*prime[j]]=true;
if (i%prime[j]==)
{
mu[i*prime[j]]=;
break;
}
mu[i*prime[j]]=-mu[i];
}
}
} int main()
{
//freopen("input.txt","r",stdin);
qword tot;
scanf("%lld\n",&tot);
init();
for (register int i=;i<MAXN;i++)
if (mu[i]==)
a[tota++]=i;
else if (mu[i]==-)
b[totb++]=i;
register qword l,r,mid;
register qword ans=;
l=,r=26000000000LL;
while (l+<r)
{
mid=(l+r)>>;
ans=;
for (register int i=;i<tota && (qword)a[i]*a[i]<=mid;i++)
ans=ans+mid/((qword)a[i]*a[i]);
for (register int i=;i<totb && (qword)b[i]*b[i]<=mid;i++)
ans=ans-mid/((qword)b[i]*b[i]);
if (ans>=tot)
r=mid;
else
l=mid;
}
printf("%lld\n",r); }
bzoj 2986
另一种可以理解为一个一个递推，按照+/-1容斥。
bzoj 2839 : 一个有N个元素的集合有2^N个不同子集（包含空集），现在要在这2^N个集合中取出若干集合（至少一个），使得它们的交集的元素个数为K，求取法的方案数，答案模1000000007。（是质数喔~）
这道题虽然说懂了正解，但是还是没有弄清楚最初的做法为什么错了。
考虑求大于等于i的方案数，可理解为从n个选出i个，再在另n-i个里面任意选择，由于答案的k个肯定属于这i个，所以容斥时再乘上系数C(i,k)，直接容斥即可。
这种题如果方法有问题其实是很难检查出来的，最好的方法是写暴力或者用另一种思路写。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAXN 1000100
#define MOD 1000000007
typedef long long qword;
qword fact[MAXN];
qword pow_mod(qword x,qword y)
{
qword ret=;
while (y)
{
if (y&)
ret=ret*x%MOD;
x=x*x%MOD;
y>>=;
}
return ret;
}
qword finv[MAXN];
#define C(x,y) (fact[x]*finv[y]%MOD*finv[(x)-(y)]%MOD) int main()
{
freopen("input.txt","r",stdin);
int n,m;
scanf("%d%d",&n,&m);
fact[]=;
for (register int i=;i<=n;i++)
fact[i]=fact[i-]*i%MOD;
finv[n]=pow_mod(fact[n],MOD-);
for (register int i=n-;i>=;i--)
finv[i]=finv[i+]*(i+)%MOD;
register qword ans=;
register qword tmp=;
ans+=((n-m)%==?:-)*C(n,n)*tmp%MOD*C(n,m)%MOD;
for (register int i=n-;i>=m;i--)
{
tmp=tmp*tmp%MOD;
ans+=((i-m)%==?:-)*C(n,i)*tmp%MOD*C(i,m)%MOD;
ans%=MOD;
}
//ans=h[m]*C(n,m);
printf("%lld\n",ans);
}
bzoj 2839
bzoj 1042：硬币购物一共有4种硬币。面值分别为c1,c2,c3,c4。某人去商店买东西，去了tot次。每次带di枚ci硬币，买si的价值的东西。请问每次有多少种付款方法。
很早以前做的一道经典题目，其思路很有借鉴意义。