组合数算法

今天比赛组合数一路溢出到死 (*>﹏<*) ，内心十分崩溃，痛定思痛，整理了几种算组合数的方法。

void init(int n) //n方复杂度求所有c[n][i] { for(int i=0;i<=n;i++){ c[i][0]=1; for(int j=1;j<=i;j++) c[i][j]=c[i-1][j-1]+c[i-1][j]; } }这个算法复杂度为n方，可以求出来从1到n的所有组合数c[n][i]。

<pre name="code" class="cpp">void ini(int n){ //n复杂度求C[n][i] C[0]=1; for(int i=1;i<=n;i++){ C[i]=C[i-1]*(n-i+1)/i; } }

这个算法复杂度为O（n），可以求出所有C[n][i]。

<pre name="code" class="cpp">int in(int n,int m){ //求C[n][m] int ans=1; if(n-m<m) m=n-m; for(int i=n,j=1;i>=n-m+1,j<=m;){ if(i>=n-m+1) { ans*=i; i--; } if(j<=m&&ans%j==0) { ans/=j; j++; } } return ans; }

这个算法复杂度为O（n）可以求出特定的C[n][m]。