HAOI 2016

OI&ACM, OI训练
HAOI结束了，第七，没有完成我(虐场)的目标 好吧其实还是开心自己可以进队了，继续加油吧 1 食物链 (chain) 给你\(n\)个物种和\(m\)条能量流动关系，求其中的食物链条数。 物种的名称为从\(1\)到\(n\)编号 \(m\) 行每行两个整数ai bi描述m条能 ...
Read More
DP 组合数学 拓扑排序

组合数学

OI&ACM, 数学
  1. 抽屉原理（鸽笼原理）
  2. 容斥原理
  3. 加法原理
  4. 乘法原理
  5. 排列 \(A(n,m)=\frac{n!}{(n-m)!}\)
  6. 组合 \(C(n,m)=\frac{n!}{m!\times (n-m)!}\)
    公式：
    \(C(n,m)=C(n,n-m)\)
    \(C(n,m)=C(n-1,m)+ C(n-1,m-1)\)
    \(C(n,0)+C(n,1)+\dots +C(n,n-1)+C(n,n)=2^n\)
  7. 可重复组合 方程x1+x2+…+xn=r的非负整数解的个数：
    可以理解为，将r个1排成一排，插入n-1个分隔符，把r个1分成n段，n段中的1的个数即是方程的一个解。
    插入n-1个分隔符的过程，实际上就是从n+r-1个位置中选择n-1个位置放分隔符，其余r个位置放1，
    共有\(C(n+r-1,n-1)=C(n+r-1,r)\)种
  8. Catalan数 \(\frac{C(2n,n)}{n+1}\)
  9. \(C_n^m\)中每个元素出现的次数为\(C_n^m \times m \div n=C(n-1,m-1)\)
Read More
组合数学