组合数学 —— 基本计数原理
【抽屜原理】
1.內容
把 n+1 件東西放入 n 個抽屜，則至少有一個抽屜里放兩件或兩件以上的東西。
從令一角度說，把 n-1 件東西放入 n? 個抽屜，則至少一個抽屜是空的。
2.經典應用
給出一個含有 n 個數字的序列，要找一個連續的子序列，使他們的和一定是 c 的倍數
假設 sum[i] 存儲整數序列中的前 i 項和
根據抽屜原理，以 sum 數組構造抽屜 drawer 數組，其保存的是最先出現的 sum[i] 的下標，當 sum 的一個元素第二次放入重復的抽屜時，輸出結果。
若 sum[i] 是 c 的倍數，直接輸出前 i 項即可，若 sum[i] 不是 c 的倍數，則需要計算 sum[i]%c，此時，sum[i]%c = sum[j]%c，i!=j 肯定存在，即第 j 到第 i 項數的和為 c 的倍數。
LL a[N],drawer[N]; LL sum[N]; int main(){LL c,n;while(scanf("%lld%lld",&c,&n)!=EOF&&c&&n){memset(drawer,-1,sizeof(drawer));drawer[0]=0;sum[0]=0;for(LL i=1;i<=n;i++){//計算前綴和scanf("%lld",&a[i]);sum[i]=sum[i-1]+a[i];}for(LL i=1;i<=n;i++){if(drawer[sum[i]%c]!=-1){for(LL j=drawer[sum[i]%c]+1;j<i;j++)printf("%lld ",j);printf("%lld\n",i);break;}drawer[sum[i]%c]=i;}}return 0; }【加法原理與乘法原理】
1.分類加法原理
做一件事，完成它有 n 類方式，第一類方式有 M1 種方法，第二類方式有 M2 種方法，…，第 n 類方式有 Mn 種方法，那么完成這件事共有 M1+M2+……+Mn 種方法。
例如：從北京到上海有火車、飛機、輪船 3 種方式，火車、飛機、輪船分別有 k1，k2，k3 個班次，那么從北京到上海有 k1+k2+k3 種方式可以到達。
2.分步乘法原理
做一件事，完成它要分成 n 個步驟，第一步有 M1 種不同的方法，第二步有 M2 種不同的方法，…，第 n 步有 Mn 種不同的方法，那么完成這件事共有 M1×M2×M3×…×Mn 種不同的方法。
例如：從北京乘坐火車到上海，需要轉 3 次車，每次專車分別有 k1，k2，k3 個班次，那么從北京到上海有 k1×k2×k3 種方式可以到達。
3.聯系
分類加法原理和分步乘法原理是兩個基本原理，回答的都是有關做一件事的不同方法種數的問題。
兩者區別在于：分類計數原理針對的是分類問題，其中各種方法相互獨立，用任何一種方法都可以完成這件事；分步計數原理針對的是分步問題，各步驟中的方法相互依存，只有各個步驟都完成才算完成事情。
分類要依據同一標準劃分，既必須包括所有情況，又不要交錯在一起產生重復；分步則應使各步依次完成，保證整個事件得到完成，既不得多余重復，也不缺少某一步驟。
【應用】
根據研究對象的有無，一般將組合數學分為排列問題和組合問題。
其根本不同是排列問題與元素順序有關，組合問題與元素順序無關。
在排列與組合問題中，經常會出現計數問題，解決計數問題的思路一般有以下三種：
1）只取需要的。將各種符合條件的情形枚舉出來，再利用加法原理求和。
2）先取后排。將各步符合條件的排列或組合計算出來，再根據乘法原理求積。
3）先全部取，再減去不要的。利用容斥定理，將各種符合條件的情形枚舉出來，再減去不符合條件的。
關于容斥定理：點擊這里
【例題】
總結
以上是生活随笔為你收集整理的组合数学 —— 基本计数原理的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 装箱问题（信息学奥赛一本通-T1295）
- 下一篇： 删数问题（信息学奥赛一本通-T1321）