組合せ数のいくつかの一般的な計算方法
4930 ワード
加算繰返し:o(n∗n)o(n*n)o(n∗n)
式:C(m n)Ctbinom{m}{n}C(nm)=C(m n−1)Ctbinom{m}{n−1}C(n−1 m)+C(m−1 n−1)Ctbinom{m−1}{n−1}C(n−1 m−1)
理解:これは彼を2つの状況に分けたのです:必ずある1つを選んで、ある1つを選ばないでください
乗算繰返し:o(n)o(n)o(n)o(n)
式:C(m n)Ctbinom{m}{n}C(nm)=n−m+1 mfrac{n−m+1}{m}mn−m+1*C(m−1 n)Ctbinom{m−1}{n}C(nm−1)
式:C(m n)Ctbinom{m}{n}C(nm)=C(m n−1)Ctbinom{m}{n−1}C(n−1 m)+C(m−1 n−1)Ctbinom{m−1}{n−1}C(n−1 m−1)
理解:これは彼を2つの状況に分けたのです:必ずある1つを選んで、ある1つを選ばないでください
ll C[1001][1001];
memset(C,0,sizeof(C));
for(int i=0;i<=n;i++)
{
C[i][0] = 1;
for(int j=0;j<=i;j++)
C[i][j] = C[i-1][j] + C[i-1][j-1];
}
乗算繰返し:o(n)o(n)o(n)o(n)
式:C(m n)Ctbinom{m}{n}C(nm)=n−m+1 mfrac{n−m+1}{m}mn−m+1*C(m−1 n)Ctbinom{m−1}{n}C(nm−1)
ll C(int m,int n)
{
c[0] = 1;
if(m > n-m)m = n-m; //
for(int i=1;i<=m;i++)
c[i] = (n-i+1)*c[i-1]/i;
}