# 枚舉、觀察法
`第16週社課`
## 枚舉
即窮舉，從可能的答案範圍或題目中適當的枚舉來獲得答案

Ex：找因數(ZJ a010)

有時候可以透過排序來減少枚舉的數量

Ex：給定三數字，問這三個數字能不能組成三角形的邊長(ZJ c268)

以上這段文字大部分來自去年講義。

## 暴力枚舉
用於撈部分分還有觀察性質
### 位元枚舉(01枚舉)
枚舉所有取&不取的組合

因為這種枚舉方式不在乎順序，所以實作上我們不在乎第一個取什麼，我們只在乎這些取的東西所形成的「集合」

因為不知道$n$是多少，所以用$n$層for迴圈顯然不太方便

所以實作上用遞迴（$O(2^n)$）或狀態壓縮（$O(n\times 2^n)$）

### 枚舉所有排列順序
C++內建函式：next_permutation

<!-- TO DO -->
複雜度$O(n!)$

### 枚舉所有集合(取&不取)的所有子集合
<!-- 這個要教嗎 有點毒 -->
以狀態壓縮實作

<!-- TO DO -->

複雜度$O(n\times 3^n)$

## 數學枚舉

Ex：輸出符合題目要求的數列，或是輸出-1代表該數列不存在

<!-- 有適合的CF problem作為例題嗎 -->
## 觀察法
某些想不出來的題目可以透過枚舉小測資的答案來猜測答案的規律

如果你把小測資的答案排成一個數列，這個數列可能具有某種規律

這個章節就是教你如何推這種規律

<!-- TO DO：用內插法推出原多項式 -->