# 組合數 ## n! 有多少個質因子 p ? 答案是 $$\lfloor \frac{n}{p} \rfloor + \lfloor \frac{n}{p^2} \rfloor + \lfloor \frac{n}{p^3} \rfloor \cdots$$ ```C++ // 計算 n! 中有多少個質因子 p，復雜度為 O(longn) int cal(int n, int p){ int ans=0; while(n){ ans+=n/p; n/p; } return ans; } ``` ## 組合數的計算 ### 方法一：組合數遞推公式 $$C_n^m=C_{n-1}^m+C_{n-1}^{m-1}$$ ，即 n 個不同的數中選 m 個數的方案數，等于不選第一個數，在剩下的數中選 m 個，加上選第一個數，再從剩下的數中選 m-1 個。 ```c++ int C(int n, int m){ if(m==0 || n==m) return 1; return C(n-1,m)+C(n-1,m-1); } // 記錄算過的數 int C(int n, int m){ int res[N][N]={0}; if(m==0 || n==m) return 1; return res[n][m]=C(n-1,m)+C(n-1,m-1); } ``` ### 方法二：組合數定義式變形 $$ C_n^m=\frac{n!}{m!(n-m)!}=\frac{n!/(n-m)!}{m!}=\dfrac{\dfrac{\dfrac{\dfrac{(n-m+1)}{1}\times(n-m+2)}{2}\times \cdots}{\cdots}\times(n-m+m)}{m} $$ 第 i 層的結果為 $$C_{n-m+i}^i$$ 為整數。 ```C++ // 時間復雜度為 O(m) int C(int n, int m){ int ans=1; for(int i=1;i<=m;i++){ ans=ans*(n-m+i)/i; } return ans; } ``` ## ChangeLog > 2018.09.04 初稿