CSP 初賽

主定理

對於一個遞推關係式子：$T(n) = aT(\frac{n}{b}) + f(n)$。其複雜度為：

• 如果存在常數 $\epsilon > 0$，有 $f(n) = O\left(n^{\log_{b}(a) - \epsilon} \right)$，則 $T(n) = \Theta\left(n^{\log_{b}a}\right)$。
• 如果存在常數 $\epsilon \ge 0$，有 $f(n) = \Theta\left(n^{\log_{b}a} \log^{\epsilon}n\right)$，則 $T(n) = \Theta\left(n^{\log_{b}a} \log^{\epsilon+1}n\right)$
• 如果存在常數 $\epsilon > 0$，有 $f(n) = \Omega\left(n^{\log_{b}(a)+]\epsilon} \right)$，且存在常數 $c < 1$ 以及充分大的 $n$ 使得 $af\left(\frac{n}{b} \right) \le cf(n)$，則 $T(n) = \Theta\left[f(n)\right]$

參考維基百科，與演算法導論對應章節。

其實就是找 $aT(\frac{n}{b})$ 與 $f(n)$ 兩個部分複雜度較大的。

複雜度記號

• $O$：上界
• $\Theta$：上下界
• $o$：上界（不取等的那種）
• $\Omega$：下界
• $\omega$：下界（不取等的那種）

$\mathrm{poly}(n)$ 指和 $n$ 有關的多項式，同理 $\mathrm{polylog}(n)$ 實際上就是 $\mathrm{poly}(\log n)$，即和 $\log n$ 有關的多項式。

錯排問題

考慮容斥，若存在 $i$ 個數在原來的位置上，這種情況的數量是 $\binom{n}{i}(n-i)!$，所以可以得到錯排公式：

$$\begin{aligned} D(n) &= \sum_{i=0}^{n} (-1)^{i} \binom{n}{i}(n-i)! \\ &= \sum_{i=0}^{n} (-1)^{i} \frac{n!}{i!} \\ &= n! \sum_{i=0}^{n} \frac{(-1)^{i}}{i!} \end{aligned}$$

也可以考慮遞推，對於第 $n$ 個數，假設它被放到位置 $i$ 構成錯排，考慮第 $i$ 個數的位置：

• 如果 $i$ 位於 $n$，餘下的數構成 $n-2$ 階錯排，即 $(n-1)D(n-2)$。
• 如果 $i$ 不位於 $n$，即又是一個 $n-1$ 階錯排，答案為 $(n-1)D(n-1)$。

故得到遞推公式：$D(n)=(n-1)[D(n-1)+D(n-2)]$。

OEIS: A000166。

卡特蘭數

從最經典的出棧序列計數開始。將入棧記作 -1，出棧記作 +1，可以得到一個長度為 2n 的序列，一個合法的出棧序列滿足其任意一個字首和非負，且總和為 0。

考慮統計不合法的出棧序列。對於任意一個不合法的出棧序列，找到第一個滿足字首和等於 -1，的位置 p，將 p 之前的所有數翻轉，即 -1 變為 +1，+1 變為 -1，得到一個長度為 2n 且有 n+1 個 +1，n-1 個 -1 的序列。容易得到對於任意一個有 n+1 個 +1，n-1 個 -1 的序列都能對應一個不合法的出棧序列，這是個雙射。故不合法序列的總數為 $\binom{2n}{n+1}$，總共合法序列的數量為 $\binom{2n}{n} - \binom{2n}{n+1} =\frac{\binom{2n}{n}}{n+1}$。

OEIS: A000108。

Twelvefold way

$n$ 個球，$x$ 個盒子。

$n$ 個有標號球放入 $x$ 個有標號盒子

$$x^{n}$$

$n$ 個有標號球放入 $x$ 個有標號盒子，每個盒子至多一個球

$$x^{\underline n}$$

$n$ 個有標號球放入 $x$ 個有標號盒子，每個盒子至少一個球

$$x! \begin{Bmatrix} n \\ x \end{Bmatrix}$$

第二類斯特林數統計的是不區分盒子時的數量，乘上 $x!$ 表示考慮 $x$ 個盒子的順序。

$n$ 個無標號球放入 $x$ 個有標號盒子

$$\binom{n+x-1}{x-1}$$

每個盒子預先放上一個球，即轉化為 $n+x$ 個無標號球放入 $x$ 個有標號盒子，每個盒子至少一個球。

$n$ 個無標號球放入 $x$ 個有標號盒子，每個盒子至多一個球

$$\binom{x}{n}$$

考慮哪些盒子放了球。

$n$ 個無標號球放入 $x$ 個有標號盒子，每個盒子至少一個球

$$\binom{n-1}{x-1}$$

插板法，考慮 $n$ 個球之間有 $n-1$ 個空位，在這些空位中插入 $x-1$ 個分隔。

$n$ 個有標號球放入 $x$ 個無標號盒子

$$\sum_{i=0}^{k} \begin{Bmatrix} n \\ i \end{Bmatrix}$$

盒子是可空的，所以列舉有多少個盒子空，轉化為每個盒子至少一個球的問題。

$n$ 個有標號球放入 $x$ 個無標號盒子，每個盒子至多一個球

$$[n \le x]$$

$n$ 個有標號球放入 $x$ 個無標號盒子，每個盒子至少一個球

$$\begin{Bmatrix} n \\ x \end{Bmatrix}$$

第二類斯特林數就是這樣定義的。

計算第二類斯特林數，有遞推公式：

$$\begin{Bmatrix} n \\ x \end{Bmatrix} = \begin{Bmatrix} n-1 \\ x-1 \end{Bmatrix} + x \begin{Bmatrix} n-1 \\ x \end{Bmatrix}$$

考慮第 $n$ 個球應該放在哪裡。如果它單獨放一個盒子，那麼就是轉化為 $\begin{Bmatrix} n-1 \\ x-1\end{Bmatrix}$；如果它放入一個現有的非空盒子，那麼就是 $x\begin{Bmatrix} n-1 \\ x \end{Bmatrix}$。

$n$ 個無標號球放入 $x$ 個無標號盒子

$$p_{x}(n+x)$$

每個盒子預先放上一個球，即轉化為 $n+x$ 個無標號球放入 $x$ 個有標號盒子，每個盒子至少一個球。

$n$ 個無標號球放入 $x$ 個無標號盒子，每個盒子至多一個球

$$[n \le x]$$

$n$ 個無標號球放入 $x$ 個無標號盒子，每個盒子至少一個球

$$p_{x}(n)$$

相當於將 $n$ 拆分成恰好 $x$ 個正整數的方案數。

計算 $p_{x}(n)$，有轉移方程：

$$p_{x}(n) = p_{x}(n-x) + p_{x-1}(n-1)$$

即考慮拆分方案中不存在 $1$ 和存在 $1$ 的情況。如果不存在 $1$，那麼把方案中所有數減一，轉化為 $p_{x}(n-x)$；如果存在 $1$，那麼去掉這個 $1$，轉化為 $p_{x-1} (n-1)$。

命令

就列一些常用的。我非常反感考這種東西。

• cat: 連線檔案，並輸出
• cd: 改變 shell 工作目錄
• chmod: 更改檔案許可權
• chown: 更改檔案所有者
• cp: 複製檔案
• diff: 尋找檔案差異
• echo: 輸出引數
• find: 找檔案
• grep/egrep/fgrep: 找滿足條件的行
• help: shell 內建幫助
• less/more: 閱讀器
• ln: 連結檔案
• ls: 列出檔案資訊
• man: 檢視手冊
• mkdir: 建立目錄
• mv: 移動檔案
• printf: 格式化列印引數
• pwd: 輸出當前目錄名稱
• rm: 刪除檔案
• tar: 打包檔案
• time: 報告程式執行時間與使用資源，這不是 shell 的內建命令，通常需要用 /usr/bin/time。
• time: 報告程式執行時間，這是大部分 shell 的內建命令，不同 shell 輸出格式可能不同。
• touch: 更改檔案修改時間和訪問時間，如果檔案不存在則會建立空檔案

歷史

2023 年，第 40 屆 NOI，第 29 屆 NOIp，第 35 屆 IOI，第 5 屆 CSP。

ASCII

• '0': 48
• 'A': 65
• 'a': 97

哈夫曼樹

1. 對於給定的 $n$ 個權值，先建立 $n$ 個有 $1$ 個節點的樹。
2. 不斷進行以下操作，直到剩下 $1$ 棵樹：
   1. 選取權值最小的兩棵樹 $A$ 和 $B$，將他們分別為左右子樹，構造一顆新的樹，其權值為 $A$ 的權值加 $B$ 的權值。
   2. 刪除 $A$ 和 $B$。

人

• 艾倫·圖靈：電腦科學與人工智慧之父
• 約翰·馮·諾伊曼：馮·諾伊曼結構，又稱儲存程式計算機
• 克勞德·夏農：奠定了現代資訊理論的基礎

補碼

對於一個長度為 $n$ 的二進位制數 $x$，其補碼為 $x \bmod 2^n$。