文章目錄

• • 所有集合子集數量和
  • • 結論
    • 證明
    • 枚舉子集的方法
  • 最大匹配
  • 模的次數
  • 線性基
  • 卡特蘭數
  • 樹形dp$Tip$
  • 斯特林數
  • 斐波那契冪前綴和
  • $hall$定理
  • 阿巴阿巴1
  • 狄利克雷卷積常用式子
  • 組合數學恒等式
  • 競賽圖性質
  • 一些博弈模型
  • 基礎反演
  • • • 二項式反演
      • 莫比烏斯反演
      • 歐拉反演
      • 子集反演
      • $\text{min-max}$反演
      • 斯特林數反演
  • 貝葉斯公式
  • 可重排列
  • $Other$

所有集合子集數量和

結論

$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}$$
然后二項式定理
$$?(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\left\{\begin{array}{c}m\\ k\end{array}\right\}\left(\genfrac{}{}{0ex}{}{n}{k}\right)k!$$

$$?\left\{\begin{array}{c}n\\ m\end{array}\right\}=\frac{1}{m!}\sum _{k=0}^m(?1{)}^k(\genfrac{}{}{0ex}{}{m}{k})(m?k{)}^n$$

---

斐波那契冪前綴和

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

---

$hall$定理

$2?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 ?I=id$$
$$\mu ?I=?$$
$$\mu ?id=\phi$$
$$I?I=d$$
$$i{d}^k?I={\sigma }^k$$
$$f(x)=h(x)x,f?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)?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)?G(n)=\sum _{i=1}^n\left(\genfrac{}{}{0ex}{}{n}{i}\right)(?1{)}^{n?i}F(i)$$

莫比烏斯反演

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

歐拉反演

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

子集反演

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

$\text{min-max}$反演

$$max\{S\}=\sum _{T?S}(?1{)}^{|T|+1}min\{T\}$$
$$ma{x}_{kth}\{S\}=\sum _{T?S}(?1{)}^{|T|?k}(\genfrac{}{}{0ex}{}{|T|?1}{k?1})min\{T\}$$
對期望成立
還有一個擴展就是可以將$gcd$理解為兩個共同的質因數中取$min$，$lcm$就是在共同的質因數中取$max$，就有下面的神奇擴展
$$lcm(S)=\prod _{T?S}gcd(T{)}^{(?1{)}^{|T|?k}}$$

斯特林數反演

沒怎么見過這個東西
$$F(n)=\sum _{i=1}^n\left\{\begin{array}{c}n\\ i\end{array}\right\}G(i)?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)?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)?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)?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

總結

以上是生活随笔為你收集整理的学习手记（2020/8/19~2021/3/19）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。