求出o(logn )组合数
fac [ maxn ]={ 1，1，2 }； LLc(intn，int m ) return(fac[n]*quickpow ) (fac[n-m] ) % mod，mod - 2 ) ) mod； }for(intI=3； i maxn； I ) fac[I]=(I*fac[I-1] ) % mod； o(n )2)递归求组合数
for(intI=0； i maxn； I ) { CC[i][0]=CC[i][i]=1； for(intj=1； j i； j ) { cc [ I ] [ j ]=(cc [ I-1 ] [ j ] cc [ I-1 ] [ j-1 ] ) % mod； }重复组合(无限) ) ) ) ) ) ) ) )。
n种不同球，每个球的个数无限，从中选出k个出来，组合数为(c _ { NK1 } ^ { k }。
不相邻的数组
从1 ~ n的n个自然数中选择k个，该k个中，任意2个个数不相邻的个数的组合为(c _ { nk1 } ^ { k }。
资料来源： https://blog.csdn.net/big tiao 097/article/details/77242624
CNM=cn1 m1 cn1 MC _ n ^ m=c _ { n-1 } ^ { m-1 } c _ { n-1 } ^ { m } CNM=cn1 m1 cn1 m
mcnm=ncn 1m1m c _ n ^ m=NC _ { n-1 } ^ { m-1 } mcnm=ncn1m 1
C n 0 C n 1 C n 2
… … + C n n = 2 n C_n^0+C_n^1+C_n^2+……+C_n^n = 2^n Cn0+Cn1+Cn2+……+Cnn=2n1 C n 1 + 2 C n 2 + 3 C n 3 + … … + n C n n = n 2 n − 1 1C_n^1+2C_n^2+3C_n^3+……+nC_n^n =n2^{n-1} 1Cn1+2Cn2+3Cn3+……+nCnn=n2n−1
1 2 C n 1 + 2 2 C n 2 + 3 2 C n 3 + … … + n 2 C n n = n ( n + 1 ) 2 n − 2 1^2C_n^1+2^2C_n^2+3^2C_n^3+……+n^2C _n^n =n(n+1)2^{n-2} 12Cn1+22Cn2+32Cn3+……+n2Cnn=n(n+1)2n−2
C n 1 1 − C n 2 2 + C n 3 3 + … … + ( − 1 ) n − 1 C n n n = 1 + 1 2 + 1 3 + … … + 1 n frac{C_n^1}{1}-frac{C_n^2}{2}+frac{C_n^3}{3}+……+(-1)^{n-1}frac{C _n^n}{n} =1 + frac{1}{2}+ frac{1}{3}+……+ frac{1}{n} 1Cn1−2Cn2+3Cn3+……+(−1)n−1nCnn=1+21+31+……+n1
( C n 0 ) 2 + ( C n 1 ) 2 + ( C n 2 ) 2 + … … + ( C n n ) 2 = C 2 n n (C_n^0)^2+(C_n^1)^2+(C_n^2)^2+……+(C _n^n)^2 = C_{2n}^n (Cn0)2+(Cn1)2+(Cn2)2+……+(Cnn)2=C2nn