# 容斥总结

### 定义

$$|S_1 \cup S_2|=|S_1|+|S_2|-|S_1 \cap S_2|$$

$$|S_1 \cup S_2 \cup S_3|=|S_1|+|S_2|+|S_3|-|S_1 \cap S_2|-|S_1 \cap S_3|-|S_2 \cap S_3|+|S_1 \cap S_2 \cap S_3|$$

\begin{aligned}
|S_1 \cup S_2 \cup \cdots \cup S_n| & = \sum_{i}|S_i| -\sum_{i< j}|S_i \cap S_j|+\sum_{i< j< k}|S_i \cap S_j \cap S_k|-\cdots \\
& \cdots +(-1)^{n-1}|S_1 \cap S_2 \cap \cdots \cap S_n|
\end{aligned}

$$times=C_m^1-C_m^2+\cdots (-1)^{m-1}C_m^m$$

$$times=-((\sum_{i=0}^m(-1)^iC_m^i)-C_m^0)$$

$$times=-((1-1)^m-1)$$

$$|S_1 \cap S_2 \cap \cdots \cap S_n|=|U|-|S_1 \cup S_2 \cup \cdots \cup S_n|$$

### 例题

#### 题解

#include <cstdio>
#define mod 1000007
using namespace std;
int c[10001][510],T,n,m,k;
void init()
{
c[0][0]=1;
for (int i=1;i<=500;i++)
{
c[i][0]=1;
for (int j=1;j<=i;j++)
c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
}
}
int C(int n,int m)
{
if (n<m)
return 0;
return c[n][m];
}
main()
{
init();
scanf("%d",&T);
for (int cs=1;cs<=T;cs++)
{
scanf("%d%d%d",&n,&m,&k);
if (k==1)
{
printf("Case %d: 0\n",cs);
continue;
}
int ans=0;
for (int s=0;s<=(1<<4)-1;s++)
{
int x=n,y=m,cnt=0;
for (int i=0;i<2;i++)
if (s&(1<<i))
x--,cnt++;
for (int i=2;i<4;i++)
if (s&(1<<i))
y--,cnt++;
if (cnt&1)
ans=(ans-C(x*y,k))%mod;//,printf("-%d %d\n",x,y);
else
ans=(ans+C(x*y,k))%mod;//,printf("+%d %d\n",x,y);
}
//      int ans=(((((((((C(n*m,k)-C((n-1)*m,k)*2)%mod-C((m-1)*n,k)*2)%mod+C((n-2)*m,k))%mod+C((m-2)*n,k))%mod+C((n-1)*(m-1),k)*4)%mod-C((n-2)*(m-1),k)*2)%mod-C((m-2)*(n-1),k)*2)%mod+C((n-2)*(m-2),k))%mod)%mod;
printf("Case %d: %d\n",cs,(ans%mod+mod)%mod);
}

}


#### 题解

#include<cstdio>
#include<algorithm>
#include <cstdlib>
#include<vector>
#include <map>
using namespace std;

const int MAXN = 100005;
long long x[MAXN];
map <long long,int> ma;

long long multi(long long a, long long b, long long p) {
long long ans = 0;
while(b) {
if(b&1LL) ans = (ans+a)%p;
a = (a+a)%p;
b >>= 1;
}
return ans;
}

long long qpow(long long a, long long b, long long p) {
long long ans = 1;
while(b) {
if(b&1LL) ans = multi(ans, a, p);
a = multi(a, a, p);
b >>= 1;
}
return ans;
}

bool Miller_Rabin(long long n) {
if(n == 2) return true;
int s = 30, i, t = 0;
long long u = n-1;
while(!(u & 1)) {
t++;
u >>= 1;
}
while(s--) {
long long a = rand()%(n-2)+2;
x[0] = qpow(a, u, n);
for(i = 1; i <= t; i++) {
x[i] = multi(x[i-1], x[i-1], n);
if(x[i] == 1 && x[i-1] != 1 && x[i-1] != n-1) return false;
}
if(x[t] != 1) return false;
}
return true;
}

long long gcd(long long a, long long b) {
return b ? gcd(b, a%b) : a;
}

long long Pollard_Rho(long long n, int c) {
long long i = 1, k = 2, x = rand()%(n-1)+1, y = x;
while(true) {
i++;
x = (multi(x, x, n) + c)%n;
long long p = gcd((y-x+n)%n, n);
if(p != 1 && p != n) return p;
if(y == x) return n;
if(i == k) {
y = x;
k <<= 1;
}
}
}

void find(long long n, int c) {
if(n == 1) return;
if(Miller_Rabin(n)) {
ma[n]++;
return;
}
long long p = n, k = c;
while(p >= n) p = Pollard_Rho(p, c--);
find(p, k);
find(n/p, k);
}
long long n,k,a,b,rt[1010],tot;
long long ge(long long n)
{
long long ans=0;
for (int i=0;i<=(1<<tot)-1;i++)
{
int temp=1,cnt=0;
for (int j=0;j<tot;j++)
if (i&(1<<j))
temp*=rt[j+1],cnt++;
//      if (temp==1) continue;
if (cnt&1)
ans=ans-n/temp;
else
ans=ans+n/temp;
}
return ans;
}
main()
{
int T;
scanf("%d",&T);
for (int cs=1;cs<=T;cs++)
{
scanf("%lld%lld%lld",&a,&b,&n);
ma.clear();tot=0;
long long ans=0;
find(n,1242);
for(map<long long, int>::iterator c = ma.begin(); c != ma.end();)
{
long long x1=c->first,x2=c->second,temp=n,tans=0,te=0;
c++;
rt[++tot]=x1;
}
printf("Case #%d: %lld\n",cs,ge(b)-ge(a-1));
}
}


1 2 5 10 2
3 2 3 1 10
1000 2 2 2 900

4
27

di,s<=100000

tot<=1000

#### 题解

dp一下搞出来。$f[i]=\sum_{j=1..4}f[i-c[j]]$

#include <cstdio>
#define int long long
using namespace std;
int c[5],d[5],T,x,f[100010];
void init()
{
f[0]=1;
for (int i=1;i<=4;i++)
for (int j=c[i];j<=100000;j++)
f[j]+=f[j-c[i]];
}
main()
{
scanf("%d%d%d%d%d",&c[1],&c[2],&c[3],&c[4],&T);
init();
while(T--)
{
int ans=0;
scanf("%d%d%d%d%d",&d[1],&d[2],&d[3],&d[4],&x);
for (int i=0;i<=(1<<4)-1;i++)
{
int now=x,cnt=0;
for (int j=0;j<4;j++)
if (i&(1<<j))
now-=c[j+1]*(d[j+1]+1),cnt++;
if (now<0)  continue;
if (cnt&1)
ans-=f[now];
else
ans+=f[now];
}
printf("%lld\n",ans);
}
}


1 10

2

#### 题解

#include <cstdio>
#include <algorithm>
using namespace std;
long long cnt,ans[5010],a,b,data[5010],tot,anss;
void dfs(long long now,long long n)
{
if (now)
ans[++cnt]=now;
if (now*10+6<=n)
dfs((long long)now*10+6,n);
if (now*10+8<=n)
dfs((long long)now*10+8,n);
}
long long gcd(long long a,long long b){return b?gcd(b,a%b):a;}
bool comp(long long a,long long b)
{
return a>b;
}
void work(long long now,long long cnt,long long lcm)
{
if(now>tot)
if(cnt)
if(cnt&1)
anss+=(long long)(b/lcm-(a-1)/lcm);
else
anss-=(long long)(b/lcm-(a-1)/lcm);
else;
else
{
work(now+1,cnt,lcm);
long long gcdd=gcd(data[now],lcm);
if(data[now]/gcdd<=b/lcm)
work(now+1,cnt+1,lcm/gcdd*data[now]);
}
}
main()
{
scanf("%lld%lld",&a,&b);
dfs(0,b);
sort(ans+1,ans+1+cnt);
for (int i=1;i<=cnt;i++)
{
data[++tot]=ans[i];
for (int j=1;j<tot;j++)
if (ans[i]%data[j]==0)
{
tot--;
break;
}
}
sort(data+1,data+1+tot,comp);
work(1,0,1);
printf("%lld\n",anss);
//  printf("%d",find(b)-find(a-1));
}


#### bzoj2393

##### Description

~Cirno发现了一种baka数，这种数呢~只含有2和⑨两种数字

##### Input

( 1 < L < R < 10^10)

1 100

##### Sample Output

58

#include <cstdio>
#include <algorithm>
using namespace std;
long long gcd(long long a,long long b){return b?gcd(b,a%b):a;}
long long a[5010],data[5010],cnt,tot,l,r,ans;
void finds(long long now)
{
if (now) a[++cnt]=now;
if (now*10+2<=r) finds(now*10+2);
if (now*10+9<=r) finds(now*10+9);
}
void dfs(long long now,long long cnt,long long lcm)
{
if (now>tot)
if (cnt)
if (cnt&1) ans+=(long long)(r/lcm)-((l-1)/lcm);
else ans-=(long long)(r/lcm)-((l-1)/lcm);
else;
else
{
dfs(now+1,cnt,lcm);
long long g=gcd(lcm,data[now]);
if (data[now]/g<=r/lcm)
dfs(now+1,cnt+1,lcm/g*data[now]);
}
}
main()
{
scanf("%d%d",&l,&r);
finds(0);
sort(a+1,a+1+cnt);
for (long long i=1;i<=cnt;i++)
{
data[++tot]=a[i];
for (long long j=1;j<tot;j++)
if (a[i]%data[j]==0)
{
tot--;break;
}
}
for (long long i=1;i<=tot/2;i++)swap(data[i],data[tot-i+1]);
dfs(1,0,1);
printf("%lld\n",ans);
}


### 恰好k个的容斥

$$=\ \ge k个\ -\ \ge k+1个\ +\ \ge k+2个\ …$$

### 证明

\begin{align} &= \sum_{i=k}^x (-1)^{i-k}\binom{i}{k} \binom{x}{i} \\ &= \binom{x}{k} \sum_{i=k}^x (-1)^{i-k} \binom{x-k}{x-i}\\ &= \binom{x}{k} \sum_{j=0}^{x-k} \binom{x-k}{j} \\ &= [x==k] \end{align}