#
記錄寫過的dp題目，并分類，嘗試總結出某類題目的一般模型.
(題目前打*的未編程驗證)
【線性模型】
Tyvj 1049 最長不下降子序列問題 [O(n^2) [還存在基于二分查找的O(nlogn)算法]]
- [狀態] f[i]表示從1到i的最長不下降子序列. 最大值需更新.
- [方程] if(a[j]<=a[i]) f[i] = max{f[j]} (0<j<i, 1<i<=n)
NOIp 2004 合唱隊形 [O(n^2), 雙向最長上升子序列]
- [方程] f[i] = max{f[j]}+1 , 枚舉k(0<=k<=n).
Rqnoj 164 最長公共子串 [記錄方案 子串連續 O(n^2)]
- [狀態] f[i][j]表示 子串A第i個字符 和 子串B第j個字符 前 公共子序列長度
- [方程] f[i][j] = f[i-1][j-1]+1(a[i]=b[j],a[i-1]=b[j-1])|max{f[i-1][j],f[i][j-1]}
UVa 111/10405 [最長公共子序列問題,O(n^2). 可以使用滾動數組降至O(n).]
- [狀態] f[i][j]表示 子串A第i個字符 和 子串B第j個字符 前 公共子序列長度
- [方程] f[i][j] = f[i-1][j-1]+1(a[i]=b[j])|max{f[i-1][j],f[i][j-1]}
UVa 507 [最大連續和,O(n).]
- [狀態] f[i]表示當前子序列和(非負)
- [方程] f[i]=max{f[i-1]+a[i], a[i]},遞推過程中需更新最大值.
【矩陣模型】
*UVa 10285 滑雪 [記憶化搜索,最長下降子序列二維版本]
- [狀態] f[i][j]表示從(i,j)開始的最長下降子序列長度.
- [方程] f[i][j] = max{f[i-1][j], f[i][j-1], f[i+1][j], f[i][j+1]}+1(f[i][j]>f[i-1][j]..)
UVa 108
- 最大矩陣和，O(n^3)，方程不會. 最大連續和的二維版本.
NOIp 2000 方格取數 O(n^4)
- [狀態] f[i][j][k][l]表示兩人分別到(i,j)、(k,l)所取過的數的和.G[i][j]表示方格里的數.
- [方程] f[i][j][k][l] = max{f[i-1][j][k-1][l], f[i-1][j][k][l-1], f[i][j-1][k-1][l], f[i][j-1][k][l-1]}+G[i][j]+(i==k&&j==l ? 0 : G[k][l])
NOIp 2008 傳紙條
(1) O(n^4)
- [狀態] f[x1][y1][x2][y2] 表示從出發點分別到(x1,y1)、(x2,y2)取的最大值.G[x][y]表示該格的數.
- [方程] f[x1][y1][x2][y2] = max{f[x1-1][y1][x2-1][y2],f[x1-1][y1][x2][y2-1],f[x1][y1-1][x2-1][y2],f[x1][y1-1][x2][y2-1]}+G[x1][y1]+G[x2][y2](如果位置不重復)
- [一個重要優化] 顯然有y2=x1+y1-x2(y2>0),因而時間復雜度可以降到O(n^3).Cena顯示總用時從近4s降到近0.3s，效果明顯.
*(2) O(n^3)
- [狀態] f[p][x1][x2],p表示經過的格子數.
- [方程] f[p][x1][x2]=max{f[p-1][x1-1][x2-1],f[p-1][x1-1][x2],f[p-1][x1][x2-1],f[p-1][x1][x2]}+G[x1][p-x1]+G[x2][p-x2](如果位置不重復)
USACO 5.3.4/3.3.4 [矩陣dp,O(n^2)]
- [狀態] f[i][j]表示以(i,j)為右下角的正方形最大邊長
- [方程] f[i][j] = min{f[i-1][j], f[i-1][j-1], f[i][j-1]}+1 (0<=i,j<n)
- [預處理] 若G[i][j]=1則f[i][j]=1.
【背包問題】
USACO 3.3.2
- [狀態] f[a1][a2][a3][a4][a5]為買a1件物品1,a2件物品2,a3件物品3,a4件物品4,a5件物品5時，所需的最少價格
- [方程] f[a1][a2][a3][a4][a5] = min{f[a1-p[i][1][a2-p[i][2][a3-p[i][3][a4-p[i][4]][a5-p[i][5]+p[i][0]} (0<i<=s, ak-p[i][k]>=0,p[i][0]是優惠后的價格)
- [邊界條件] f[0][0][0][0][0]=0;
- USACO官方解法很有啟發性，用最短路，把每種狀態[a1][a2][a3][a4][a5]（a1件物品1,a2件物品2,a3件物品3,a4件物品4,a5件物品5）看成一個點，則至多7776個點，而每個優惠就是一條邊，則至多105條邊。 接下來就是求[0,0,0,0,0]到目標狀態的最短路，用Dijkstra(Heap優化)即可.
USACO 3.1.2 [完全背包問題, O(n)或O(n^2).]
- [狀態] f[i][j]表示放入第i個物體后剩余體積為j
- [方程] f[i][j] = f[i-1][j] + f[i][j-c[i]]+w[i]
USACO 3.1.6 [完全背包問題,O(n).]
- [狀態] f[i]表示湊成i分郵資的最少郵票數.
- [方程] f[i] = min{f[i-v[j]]+1} (i-v[j] >= 0, 0<=i<n, f[0] = 0).
USACO 2.3.4
- [狀態] f[i,j]表示前i種貨幣構成j的方法數，用c[i]記錄貨幣的面值.
- [方程] f[i,j]=f[i-1,j]; 不用第i種貨幣
f[i,j]=f[i-1,j]+f[i,j-c[i]] 用第i種貨幣，j>=c[i]
【樹形】
USACO 2.3.2
- [狀態] f[i,j]表示用i個點組成深度最多為j的二叉樹的方法數，則：
- [方程] f[i,j]=∑(f[k,j-1]×f[i-1-k,j-1])(k∈{1..i-2})
- [邊界] f[1,i]=1
- 我們要求的是深度恰好為K的方法數S，易知S=f[n,k]-f[n,k-1]。但需要注意的是，如果每次都取模，最后可能會有f[n,k]<f[n,k-1],所以可以用S=(f[n,k]-f[n,k-1]+v) mod v
【其他類型】
USACO 1.5.1 [數字三角形]
- [狀態] f[i][j]表示從(i,j)開始經過的數字的最大和
- [方程] f[i][j] = max{f[i+1][j], f[i+1][j+1]}+a[i][j]
USACO 3.3.5 [博弈問題]
- [狀態] s[i][j]表示從i加到j的和, 枚舉l=j-i. f[i][j]表示從i到j先取者能得到的最大數字和.
- [方程] f[i][j] = s[i][j] - min{f[i+1][j], f[i][j-1]}
USACO 3.2.2
- [狀態] f[n][m]表示至多m個1的n位二進制數數量
- [方程] f[n][m] = f[n-1][m] + f[n-1][m-1] (f[0][m] = 1)
數據范圍很小，暴力枚舉即可.
一開始想復雜了，認為需要枚舉出所有符合條件的數字，然后調整順序，尋找等式 = =
事實上只需要枚舉前兩個數，然后判斷是否符合條件即可.考慮24的情況，若B為1，則還剩下18根火柴.又A<C,所以A為1111.因而只要在[0,1111]內枚舉A、B即可.復雜度不會算.
如果范圍更大的話，可以令A<=B，枚舉A、B.操作數大約是原來的一半.進一步的優化想不到了..
1
#include<stdio.h>
2#include<iostream>
3using namespace std;
4
int num[] = 
{6, 2, 5, 5, 4, 5, 6, 3, 7, 6}, t[2230] = {0};
5int main(){
6
int n, i, j, ans = 0;
7 scanf("%d", &n);
8
for (i = 0; i < 2230; i++){
9 int tmp = i;
10 t[i] += num[tmp%10];
11 while (tmp/10){
12 tmp /= 10;
13 t[i] += num[tmp%10];
14
}
15 }
16 for (i = 0; i < 1112; i++)
17 for (j =0; j < 1112; j++)
18 if (t[i]+t[j]+t[i+j]+4 == n) ans++;
19 printf("%d\n", ans);
20
}
21
http://www.cnblogs.com/dudu/articles/495718.html
詳細步驟請看：http://space.cnblogs.com/forum/topic/8550/。
Windows Live Writer配置步驟：
1、在菜單中選擇"Weblog";，然后選擇"Another Weblog Service"。
2、在Weblog Homepage URL中輸入你的Blog主頁地址。
3、輸入用戶名與密碼。
4、在“Type of weblog that you are using”中選擇“Custom(Metaweblog API)”。
5、“Remote posting URL for your weblog”中輸入“http://m.shnenglu.com/Blog名/services/metaweblog.aspx”。
使用注意：用Windows Live Writer發布之后，Windows Live Writer并不改變當前窗口的狀態(也沒有明顯的提示)，在當前窗口中會將剛發布的隨筆處于編輯狀態，如果修改并發布，會直接修改剛發布的隨筆內容。
和2000的方格取數如出一轍.數據加強了一點，如果是裸的四維dp可能會超時(80).所以需要優化.
1.普通的四維做法
【狀態】f[x1][y1][x2][y2] 表示從出發點分別到(x1,y1)、(x2,y2)取的最大值.G[x][y]表示該格的數.
【方程】f[x1][y1][x2][y2] = max{f[x1-1][y1][x2-1][y2],f[x1-1][y1][x2][y2-1],f[x1][y1-1][x2-1][y2],f[x1][y1-1][x2][y2-1]}+G[x1][y1]+G[x2][y2](如果位置不重復)
【一個重要優化】顯然有y2=x1+y1-x2(y2>0),因而時間復雜度可以降到O(n^3).Cena顯示總用時從近4s降到近0.3s，效果明顯.
2.三維做法(參考官方題解)
【狀態】f[p][x1][x2],p表示經過的格子數.
【方程】f[p][x1][x2]=max{f[p-1][x1-1][x2-1],f[p-1][x1-1][x2],f[p-1][x1][x2-1],f[p-1][x1][x2]}+G[x1][p-x1]+G[x2][p-x2](如果位置不重復)
未編程驗證.
3.更優化的做法
dy神牛指出，進一步的優化需要用到最小費用最大流.(NOIP絕對超綱,可以確定不會更深了.)
【Code】
1 #include<stdio.h>
2 #include<iostream>
3 using namespace std;
4 int f[52][52][52][52] = {0}, n, G[52][52];
5 int max(int a, int b, int c, int d){
6 if (a < b) a= b;
7 if (a < c) a= c;
8 if (a < d) a= d;
9 return a;
10 }
11 int main(){
12 int m, n, i, j, k, l;
13 scanf("%d%d", &m, &n);
14 for (i = 1; i <= m; i++)
15 for (j = 1; j <= n; j++)
16 scanf("%d", &G[i][j]);
17 for (i = 1; i <= m; i++)
18 for (j = 1; j <= n; j++)
19 for (k = 1; k <= m; k++){
20 if (i+j-k > 0) l = i+j-k; else continue;
21 f[i][j][k][l] = max(f[i-1][j][k-1][l], f[i-1][j][k][l-1], f[i][j-1][k-1][l], f[i][j-1][k][l-1])+G[i][j]+G[k][l];
22 if (i == k && j == l) f[i][j][k][l] -= G[i][j];
23 }
24 printf("%d\n", f[m][n][m][n]);
25 }
26
簡單dp，難點在于狀態的表示.
題目可以看做兩人同時取數，這樣就避免了后效性，可以用dp做了.
【狀態】f[i][j][k][l]表示兩人分別到(i,j)、(k,l)所取過的數的和.G[i][j]表示方格里的數.
【方程】f[i][j][k][l] = max{f[i-1][j][k-1][l], f[i-1][j][k][l-1], f[i][j-1][k-1][l], f[i][j-1][k][l-1]}+G[i][j]+(i==k&&j==l ? 0 : G[k][l])
1次WA.
#01: Accepted (75ms, 384KB)
#02: Accepted (0ms, 384KB)
#03: Accepted (0ms, 384KB)
#04: Accepted (28ms, 384KB)
【Code】
1 #include<stdio.h>
2 #include<iostream>
3 using namespace std;
4 int f[12][12][12][12] = {0}, n, G[12][12];
5 int max(int a, int b, int c, int d){
6 if (a < b) a= b;
7 if (a < c) a= c;
8 if (a < d) a= d;
9 return a;
10 }
11 int main(){
12 int a, b, c, i, j, k, l;
13 scanf("%d", &n);
14 for(;;){
15 scanf("%d%d%d", &a, &b, &c);
16 if (a || b || c) G[a][b] = c;
17 else break;
18 }
19 for (i = 1; i <= n; i++)
20 for (j = 1; j <= n; j++)
21 for (k = 1; k <= n; k++)
22 for (l = 1; l <= n; l++){
23 f[i][j][k][l] = max(f[i-1][j][k-1][l], f[i-1][j][k][l-1], f[i][j-1][k-1][l], f[i][j-1][k][l-1])+G[i][j]+G[k][l];
24 if (i == k && j == l) f[i][j][k][l] -= G[i][j];
25 }
26 printf("%d\n", f[n][n][n][n]);
27 }
28
[地址]http://hi.baidu.com/yali79/blog/item/3d231901230291007aec2c71.html
21世紀NOIP提高組復賽考察點詳細分析
By hpfdf @YALI
引用資料:
NOIP2000~2009原題。
| 題目編號 | 題目名 | 主考察點 | 知識點 | 系數 |
| NOIP-2000-A | 進制轉換 | 數學 | 初等代數,找規律 | 0.6 |
| NOIP-2000-B | 乘積最大 | 動態規劃 | 資源分配DP | 0.7 |
| NOIP-2000-C | 單詞接龍 | 搜索 | DFS,字符串,模擬 | 0.5 |
| NOIP-2000-D | 方格取數 | 動態規劃 | 多維狀態 | 0.6 |
| NOIP-2001-A | 一元三次方程求解 | 數學 | 數學,枚舉,實數處理 | 0.5 |
| NOIP-2001-B | 數的劃分 | 動態規劃 | 資源分配DP,多維狀態DP | 0.7 |
| NOIP-2001-C | 統計單詞個數 | 動態規劃 | 資源分配DP,字符串 | 0.3 |
| NOIP-2001-D | Car的旅行路線 | 圖論 | 最短路,實數處理 | 0.7 |
| NOIP-2002-A | 均分紙牌 | 貪心 | 貪心,模擬 | 0.8 |
| NOIP-2002-B | 字串變換 | 搜索 | BFS,字符串 | 0.5 |
| NOIP-2002-C | 自由落體 | 數學 | 數學,物理,模擬,實數處理 | 0.6 |
| NOIP-2002-D | 矩形覆蓋 | 構造 | 動態規劃/貪心/搜索剪枝 | 0.2 |
| NOIP-2003-A | 神經網絡 | 圖論 | 拓撲排序,第推 | 0.4 |
| NOIP-2003-B | 偵探推理 | 模擬 | 枚舉,模擬,字符串 | 0.5 |
| NOIP-2003-C | 加分二叉樹 | 動態規劃 | 樹,區間DP | 0.4 |
| NOIP-2003-D | 傳染病控制 | 構造 | 隨機貪心/搜索剪枝 | 0.2 |
| NOIP-2004-A | 津津的儲蓄計劃 | 模擬 | 模擬 | 0.9 |
| NOIP-2004-B | 合并果子 | 貪心 | 最優哈夫曼樹,排序 | 0.7 |
| NOIP-2004-C | 合唱隊形 | 動態規劃 | 子序列DP | 0.7 |
| NOIP-2004-D | 蟲食算 | 搜索 | 搜索剪枝,模擬 | 0.2 |
| NOIP-2005-A | 誰拿了最多獎學金 | 模擬 | 模擬,字符串 | 0.8 |
| NOIP-2005-B | 過河 | 動態規劃 | 子序列DP,貪心優化 | 0.2 |
| NOIP-2005-C | 篝火晚會 | 數學 | 置換群,貪心 | 0.2 |
| NOIP-2005-D | 等價表達式 | 模擬 | 字符串,抽樣檢測,表達式 | 0.3 |
| NOIP-2006-A | 能量項鏈 | 動態規劃 | 區間環DP | 0.6 |
| NOIP-2006-B | 金明的預算方案 | 動態規劃 | 資源分配DP,構造 | 0.6 |
| NOIP-2006-C | 作業調度方案 | 模擬 | 模擬 | 0.7 |
| NOIP-2006-D | 2^k進制數 | 動態規劃 | 動態規劃/組合數學,高精度 | 0.5 |
| NOIP-2007-A | 統計數字 | 模擬 | 排序 | 1.0 |
| NOIP-2007-B | 字符串的展開 | 模擬 | 字符串,模擬 | 0.7 |
| NOIP-2007-C | 矩陣取數游戲 | 動態規劃 | 區間DP,高精度 | 0.6 |
| NOIP-2007-D | 樹網的核 | 圖論 | 最短路,樹的直徑 | 0.4 |
| NOIP-2008-A | 笨小猴 | 模擬 | 質數判斷,字符串 | 1.0 |
| NOIP-2008-B | 火柴棒等式 | 模擬 | 枚舉,優化/開表 | 0.8 |
| NOIP-2008-C | 傳紙條 | 動態規劃 | 多維狀態DP | 0.7 |
| NOIP-2008-D | 雙棧排序 | 構造 | 枚舉,貪心/二分圖 | 0.4 |
| NOIP-2009-A | 潛伏者 | 模擬 | 字符串,模擬 | 0.9 |
| NOIP-2009-B | Hankson的趣味題 | 數學 | 初等數論,質因數,組合數學 | 0.4 |
| NOIP-2009-C | 最優貿易 | 圖論 | 最短路 | 0.5 |
| NOIP-2009-D | 靶形數獨 | 搜索 | 搜索優化 | 0.3 |
動態規劃：12
模擬：10
數學：5
圖論：4
搜索：4
構造：3
貪心：2
【動態規劃】平均難度系數：0.55
次項為歷屆NOIP考察次數最多的知識點。
主要有 1.區間模型 2.子序列模型 3.資源分配模型 以及一些簡單的多維狀態設計技巧。
動態規劃可以與圖,樹,高精度等知識點配合出題。
【模擬】平均難度系數：0.76
平均每屆NOIP都會出現1個模擬題。
這種題一般算法很簡單，需要選手細心理解題目意思，注意細節。考察選手的代碼實現能力。
【數學】平均難度系數：0.46
需要掌握質數及其性質，基礎的實屬操作，加法原理和乘法原理。此類題需要選手對數學規律的靈感。
【圖論】平均難度系數：0.50
歷屆考察點基本上都是1.最短路問題 和 2.特殊圖的性質 。特殊圖包括樹，拓撲圖，二分圖等。
歷屆NOIP在圖論上的考察并不是很多。
【搜索】平均難度系數：0.38
歷屆搜索題一般都比較難，搜索算法本身簡單，于是題目會提高選手對其他方面的要求。
主要有搜索優化和模擬。寫搜索題時應該以盡量多得分為目標。
【構造】平均難度系數：0.27
構造類題目一般沒有明確的算法，需要選手仔細分析題目的實質，并得出解法。
這個解法通常不是唯一的。有時一個好的貪心可以得相當多的分。有時搜索剪枝可以很大的提高效率。
同樣以多得分為目標。
【貪心】平均難度系數：0.75
此類題需要選手對算法的直覺，貪心正確性一旦被證明，通常題目就很簡單了。
(×)友情提醒：
考場上沒有標示每道題屬于什么類型，光分析歷屆類型是沒用的。
想要得高分，還得多做題。
http://www.cnblogs.com/TerryFeng/archive/2009/01/30/1381483.html
由于cppblog和cnblogs使用的系統相同，因而可以使用Windows Live Writer直接編輯.
拓撲排序
雖然AC了，但還是覺得自己很不在狀態.
1#include<stdio.h>
2#include<string.h>
3bool G[110][110];
4int in[110], m, n;
5struct stack{
6 int q[110], t;
7 stack() {memset(q, 0, sizeof(q)); t= 0;}
8 void push(int x) {q[++t] = x;}
9 int pop() {return q[t--];}
10 bool empty() {return t ? 0 : 1;}
11};
12void toposort(){
13 stack s;
14 int p[110], t = 0, i, j;
15 bool flag[110] = {0};
16 for (;;){
17 if (t == m) break;
18 for (i = 1; i <= m; i++)
19 if (!in[i] && !flag[i]) s.push(i);
20 while (!s.empty()){
21 i = s.pop();
22 p[++t] = i;
23 flag[i] = 1;
24 for (j = 1; j <= m; j++)
25 if (G[i][j]) in[j]--;
26 }
27 }
28 for (i = 1; i < t; i++)
29 printf("%d ", p[i]);
30 printf("%d\n", p[t]);
31}
32int main(){
33 int i, x, y;
34 while (scanf("%d%d", &m, &n) == 2 && (m || n)){
35 memset(G, 0, sizeof(G));
36 memset(in, 0, sizeof(in));
37 for (i = 1; i <= n; i++){
38 scanf("%d%d", &x, &y);
39 G[x][y] = 1;
40 in[y]++;
41 }
42 toposort();
43 }
44}
45
由于求導在函數方面出人意料的應用，所以被迫開始復習求導. = =
1.單調性
在某一區間內f '(x)>0 => 在此區間內函數單調遞增
在某一區間內f '(x)<0 => 在此區間內函數單調遞減
2.極值
當x=a時取極值，則有f '(a)=0
3.凹凸性
f ''(x)>0 下凸曲線
f ''(x)<0 上凸曲線
貌似就這些了，不過答題格式還是一個問題...這次數學作業就當實驗算了 = =
引：“我們要把厚書讀薄，再把薄書讀厚.”
進一步的系統化將在讀完這本書后，以表格或者思維導圖的形式出現.
一、乘法原理
乘法原理討論分階段辦事過程中的計數問題.
用集合論觀點解釋：
把分階段進行的事情看作一種多重選取過程，每一個過程都是自某個集合挑選一個元素，然后考慮有多少種不同的挑選方式.
【應用】數的整除，因數分解問題
【例3】2160的正約數個數.
2160 = 2^4 * 3^3 * 5^1
則任意約數形式為2^i * 3^j * 5 ^k (0<=i<=4, 0<=j<=3, 0<=k<=1)
所以約束個數為(4+1)(3+1)(1+1)=32.
【例5】從題目中抽象出模型.
【例6】 一個結論：[u,v]=n, 令n的因子r的個數為n(r)，有k個因子.
則符合要求的數對個數為 (2n(r)+1)*..*(2n(r)+1).
需要注意的是最大公約數，是去兩數某因子的最大值.
【例7】補集思想.(排除法)
在整除性問題中，確定前n-1位，然后分類討論第n位的情況.
【例8】看了，未懂.
二、重復排列
【定義】如果在同一個n階集合(有n個元素)中依次進行k次選取，而且選過的元素還可以再選，則一共有n^k中不同的選取方式(即重復排列方式).
【應用】空間解析幾何、集合子集性質的討論
【例5】立方體{(x,y,z):0<=x,y,z<=a}頂點坐標.
證 顯然每個頂點(x,y,z)的三個坐標都是集合{0,a}的元素，所以共有2^3個不同的頂點.坐標略.
【例6】在三維歐氏空間給出9個格點(坐標值為整數)，求證其中必有兩點中點坐標為格點.
證 若兩點A(x1,y1,z1)和B(x2,y2,z2)的中點為格點，必有x1和x2，y1和y2，z1和z2和為偶數，即兩者奇偶性相同.
考慮考慮歐氏空間格點奇偶性情況可知，每個坐標值都是{奇數，偶數}中一個元素，所以格點有8種不同的奇偶性.從而，原命題由抽屜原理可證.
【例7】n階集合共有2^n個子集，2^n-1個真子集.
【例9】棋盤問題，從左下角走到右上角，n+1行，m+1列，求證f(m,n)<=2^(mn).
證 道路將城市分成mn個方塊，而路線又將方塊分成兩個子集(其中一個可能為空)，顯然不同子集個數為2^(mn).即f(m,n)<=2^(mn)，當且僅當m=n=1時等號成立.
三、排列
【定義】從n個不同的元素中有次序地選取k(1<=k<=n)個，叫做從n個不同元素中取出k個元素的一個排列.
【應用】組數問題中的“無重復數字”問題.
【例4】利用補集思想處理無重復數字問題.考慮不參加組數的數字整除情況和所有數字整除情況(聯系1.7)
【例5】逐位討論.
【例7】注意到k個數字取自不同行列(聯想皇后問題)，所以子集個數為k!，每個子集的和分行列討論，累加即可.
【例10】有2n個人參加收發電報培訓，每兩人結為一對互發互收，有多少種不同的結對方式.(搭配問題)
解 (2n-1)(2n-3)...3*1=(2n)!/(2^n*n!)
需要注意的是求和使用的思想: 先求出全部數的積，然后去掉里面的偶數.也是一種間接的方法.
四、加法原理
【集合的分劃】
若把一個集合B分成一些子集B1,B2,...,Bk，使得
(i)B1∪B2∪...∪Bk = B;
(ii)B1∩B2=∅ ,...，Bk-1∩Bk=∅.滿足這兩條性質的子集B1,B2,...,Bk，叫做B的一個分劃.
【定義】
|B|=|B1|+|B2|+...+|Bk| 加法公式
這種通過分劃計數的原理叫做加法原理.
【例1】現有長度分別為1,2,...,n的細木棍各一根，可以以它們為邊構成多少種不同的三角形?
解 以c的長度對這些三角形分類，將c=k的三角形集合記做Bk，則構成了集合B的一個分劃.
在Bk中，三角形三邊分別為a<b<k，其中k為定值，于是可將
(a,b)對應于平面中的格點.通過限制條件a<k,b<k,a+b>k我們可以知道，符合條件的格點在a=b,a+b=k,b=k三條直線圍成的三角形內,
所以若k為偶數，有|Bk|=1/4*(k-2)^2
若k為奇數，有|Bk|=1/4(k-1)(k-3)
從而可以求得|B|.(二階等差數列求和不熟)
【例2】求方程x^2-[x]^2=(x-x[x])^2在區間[1,n]中根的數目.
解
將區間[k,k+1)中根的集合記做Bk.若x∈[k,k+1)，記k=[x],p=x-[x](0<=p<1)，可得2kp=[2kp+p^2].
顯然等式兩邊為整數，所以p=0,1/2k,...,2k-1/2k，故而|Bk|=2k。
由加法原理可知，|B|=n^2-n+1
五、帶限制條件的排列問題
(i) 間接方法
【排除法】先假定不存在限制條件，求出所有情況的數目；再考慮受到限制條件，而不允許出現的情況數目.
(ii) 直接方法
【優限法】優先解決受限對象(受限對象或受限元素)的安置，然后再考慮一般對象的安置問題.
【插入法】首先安排一般元素，然后將首先元素插入到允許的位置上.(某些元素相鄰或者不相鄰)
【視一法】首先要把要求相鄰排列的元素看成一個整體，同其他元素一同排列，然后再考慮這個整體內部的元素間的排列問題.
【例8】10個節目中有6個演唱，4個舞蹈，要求每兩個舞蹈之間至少安排一個演唱.
解 反過來看問題，原命題等價于在任意兩演唱(邊界情況的話一個)中安排或不安排一個舞蹈，而這樣的可能位置共7個.所以共6!*P(7,4)種順序.
六、組合
【定義】從n個不同物件中無次序地(不計順序地)選取k個，叫做從n個物件中選k個的一個組合.
如果考慮k個物件的選取順序，可得P(n,k)=C(n,k)*k!
從而得到組合的計算公式C(n,k)=n!/k!(n-k)!
(i)C(n,n-k)=C(n,k)
(ii)C(n,k)+C(n,k-1)=C(n+1,k)