计数问题

Posted by sjj118 on 2016-12-09

一些零散的总结

计数问题是OI中很难的一类问题,往往能够考察选手的多方面能力。

计数问题的常见解法有以下几种:

  • 递推与动规
  • 容斥
  • 组合数
  • 生成函数

一道题目往往需要结合多种方法才能解决。

很多题目通过比较复杂的式子推导后往往能得出比较简洁的答案,所以找规律也是一种解题方法。

常用公式

组合数的重要公式:\(\sum_{k=0}^s\binom{k}{n}\binom{s-k}{m}=\binom{s+1}{n+m+1}\)

卡特兰数:\(C_n=\binom{2n}{n}-\binom{2n}{n-1}=\frac{1}{n+1}\binom{2n}{n}=\sum_{i=0}^{n-1}C_iC_{n-i-1}\)

一些练习