本文共 6715 字，大约阅读时间需要 22 分钟。

所有集合子集数量和

结论

$n$个点的所有子集的子集数量为$3^n$

证明

证明$:k$个点总共有$2^k$个集合，$n$个点数量为$k$的子集数量为$C_n^k$。所以答案就是$$\sum _{k=0}^n{C}_n^k{2}^k$$

$$\sum _{k=0}^n{C}_n^k{2}^k{1}^{n-k}$$ 然后二项式定理 $$\Rightarrow (1+2{)}^n=3^n$$

枚举子集的方法

for(int i=s;i>=0;i=(i-1)&s)//i-1后去掉末尾的1或者全部退位变为1

---

最大匹配

最大独立集=最小路径覆盖=点数-最大匹配

---

模的次数

对于一个数不断模上另一个数那么有

$$x\%m\{\begin{array}{c}x\%m=x\\ x\%m\le \frac{x}{2}\end{array}$$

---

线性基

• 若$d_i$在线性基内，那么$d_i$的第$i+1$位为$1$且是最高位
• 异或个数和为$2^{siz}$，推广得到异或起来小于等于$d_i$的个数为$2^x$，其中$x$表示包括$d_i$前面有多少个在线性基内的数

---

卡特兰数

$$H(n)=\sum _{i=0}^{n-1}H(i)H(n-i-1)$$

$$H(n)=C_{2n}^n-C_{2n}^{n-1}$$

前若干项（$XXY$说万一打表的时候遇到了呢）$:1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440,9694845$

---

树形dp$Tip$

$dp$时如果$f_{x,j}$中$j$的上界是$si{z}_x$，合并的复杂度是$O(n^2)$的

---

斯特林数

$$n^m=\sum _{k=0}^m\{$$

mk​}(kn​)k!

$$\Rightarrow \{$$

nm​}=m!1​k=0∑m​(−1)k(km​)(m−k)n

---

斐波那契幂前缀和

$$\sum _{i=1}^n{f}_i^2=f_i{f}_{i+1}$$

---

$hall$定理

$2\ast n$个点的二分图匹配，如果满足任意$k$个点都连接了不少于$k$个点的话，那么这张图就有完全匹配。

证明：

考虑反证，假设存在一个二分图G满足HALL定理而没有完美匹配。

那么考虑一个不在最大匹配中的X部的点，由于HALL定理其至少与Y部的一个点相连。

那么再考虑Y部的这个点，显然其一定在最大匹配中，然后根据HALL定理，这个点一定还连向另外一个X部的点。

再考虑这个X部的点，还有一个Y部的点与其相连。。。。

所以我们最后一定能推出矛盾。

故原命题得证，Q.E.D.

---

阿巴阿巴1

$$(a+b{)}^p\equiv a^p+b^p(modp)$$

---

狄利克雷卷积常用式子

$I:I[x]=1$

$id:id[x]=x$ $ϵ:ϵ[x]=[x=1]$ $\mu :$莫比乌斯函数 $\phi :$欧拉函数 $d:$约数个数函数 ${\sigma }^k:$约数$k$次方和函数 $$\phi \ast I=id$$ $$\mu \ast I=ϵ$$ $$\mu \ast id=\phi$$ $$I\ast I=d$$ $$i{d}^k\ast I={\sigma }^k$$ $$f(x)=h(x)x,f\ast id=n\sum _{d|n}h(d)$$

---

组合数学恒等式

$$k\left(\genfrac{}{}{0ex}{}{n}{k}\right)=n\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)$$

$$\frac{n!}{k!(n-k)!}k=\frac{n!}{(k-1)!(n-k)!}$$

$$\frac{(n-1)!}{(k-1)!(n-k)!}n=\frac{n!}{(k-1)!(n-k)!}$$

---

竞赛图性质

• 竞赛图满足一定有曼哈顿路径
• 竞赛图中的强连通分量满足一定有曼哈顿回路

---

一些博弈模型

• $Nim$游戏（$n$堆石头每个人轮流取$1$堆中的若干个，无法操作者败）：全部石头异或起来，为$0$则先手必败
• $Ni{m}_k$游戏（$n$堆石头每个人轮流取$k$堆中的若干个，无法操作者败）：全部石头的每一个位数分别加起来$\%k$，全是$0$则先手必败
• 反$Nim$游戏（$n$堆石头每个人轮流取$1$堆中的若干个，无法操作者胜）：全部减$1$后做$Nim$游戏，因为最后一个人可以控制奇偶
• 阶梯$Nim$游戏（$n$堆石头每个人轮流取一堆中的若干个并且让前面的所有石头加回那么多个，无法操作者败）：奇数标号的石头异或起来，为$0$则先手必败
• 分裂$Nim$游戏（$n$堆石头每个人轮流取一堆中的若干个或者将一堆分裂成两堆有石头的）：$O(a_i^2)$算出每种情况的$SG$函数然后异或起来计算

---

基础反演

二项式反演

$$F(n)=\sum _{i=1}^n\left(\genfrac{}{}{0ex}{}{n}{i}\right)(-1{)}^{i}G(i)\iff G(n)=\sum _{i=1}^n(\genfrac{}{}{0ex}{}{n}{i})(-1{)}^{i}F(i)$$

$$F(n)=\sum _{i=1}^n\left(\genfrac{}{}{0ex}{}{n}{i}\right)G(i)\iff G(n)=\sum _{i=1}^n\left(\genfrac{}{}{0ex}{}{n}{i}\right)(-1{)}^{n-i}F(i)$$

莫比乌斯反演

$$F(n)=\sum _{d|n}G(d)\iff G(n)=\sum _{d|n}\mu (d)F(\frac{n}{d})$$

$$F(n)=\sum _{n|d}G(d)\iff G(n)=\sum _{n|d}\mu (d)F(\frac{d}{n})$$

欧拉反演

$$gcd(S)=\sum _{d|x,\forall x\in S}\phi (d)$$

子集反演

$$F(S)=\sum _{T\subseteq S}G(T)\iff G(S)=\sum _{T\subseteq S}(-1{)}^{|S|-|T|}F(T)$$

$\text{min-max}$反演

$$max\{$$

S}=T⊆S∑​(−1)∣T∣+1min{

T} m a x k t h { S } = ∑ T ⊆ S ( − 1 ) ∣ T ∣ − k ( ∣ T ∣ − 1 k − 1 ) m i n { T } max_{kth}\{S\}=\sum_{T\subseteq S}(-1)^{|T|-k}\binom{|T|-1}{k-1}min\{T\} maxkth​{

S}=T⊆S∑​(−1)∣T∣−k(k−1∣T∣−1​)min{

T} 对期望成立 还有一个扩展就是可以将$gcd$理解为两个共同的质因数中取$min$，$lcm$就是在共同的质因数中取$max$，就有下面的神奇扩展 $$lcm(S)=\prod _{T\subseteq S}gcd(T{)}^{(-1{)}^{|T|-k}}$$

斯特林数反演

没怎么见过这个东西

$$F(n)=\sum _{i=1}^n\left\{\begin{array}{c}n\\ i\end{array}\right\}G(i)\iff G(n)=\sum _{i=1}^n(-1{)}^{n-i}\left[\begin{array}{c}n\\ i\end{array}\right]F(i)$$ $$F(n)=\sum _{i=n}^{\infty }(-1{)}^{n-i}\left\{\begin{array}{c}n\\ i\end{array}\right\}G(i)\iff G(n)=\sum _{i=n}^{\infty }\left[\begin{array}{c}n\\ i\end{array}\right]F(i)$$ $$F(n)=\sum _{i=1}^n\left\{\begin{array}{c}n\\ i\end{array}\right\}G(i)\iff G(n)=\sum _{i=1}^n(-1{)}^{n-i}\left[\begin{array}{c}n\\ i\end{array}\right]F(i)$$ $$F(n)=\sum _{i=n}^{\infty }(-1{)}^{n-i}\left\{\begin{array}{c}n\\ i\end{array}\right\}G(i)\iff G(n)=\sum _{i=n}^{\infty }\left[\begin{array}{c}n\\ i\end{array}\right]F(i)$$

后面单位根反演还没学

---

贝叶斯公式

---

可重排列

我是什么废物怎么晚了才会这个啊？

$k$种物品第$i$个有$a_i$个时全排列的方案是 $$\frac{({\sum }_{i=1}^n{a}_i)!}{{\prod }_{i=1}^n(a_i!)}$$ 可以理解为先全部排列一次然后去掉里面同色的排列方案？

---

$Other$

• 正难则反
• 斜率优化中等将于一个变量有关的丢一起即可
• $dp$转移可以把麻烦转移的一个值让其他的都加上，然后让其他转移时减去那个值
• 证明一种最优化做法正确时可以证明$res\ge ans$和$res\le ans$
• To be continue

转载地址：http://kcwaf.baihongyu.com/