# 容斥总结

### 定义

$$|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|$$

### 例题

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]]$

1 10

2

#### bzoj2393

##### Description

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

##### Input

( 1 < L < R < 10^10)

1 100

58

### 恰好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}

×