ACM会用到的一点数学知识集锦
~1.费马小定理:a^pmodp=a(p为素数,且a不是p的倍数) 2.数n的约数个数: n分解因数为p1^s1*p2^s2*……pm^sm 则约数个数为(s1+1)*(s2+1)*……*(sm+1) 3.Fibonacci数通项公式:Fn=round((1+√5)/2)^n/√5 4.Catalan数通项公式:Cn=C(2n-2,n-1)/n 递归式:Cn=∑Ci*C(n-i)(i=1..n-1,C1=C2=1) 5.第二类Stirling数:S(n,k)表示n个元素的集合拆分成k部分的数 S(n,k)=S(n-1,k-1)+k*S(n-1,k) 6.整数分拆:P(n,k)-整数n分成k部分的数 P(n,k)=P(n-1,k-1)+P(n-k,k) 7.方程x1+x2+……+xk=n(xi>=0)的解的个数:C(n+k-1,k-1) 方程x1+x2+……+xk=n(xi>0)的解的个数:C(n-1,k-1)