一些零散的总结
计数问题是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}\)
一些练习
- BZOJ2111 [ZJOI2010]排列计数
- BZOJ2425 [HAOI2010]计数
- BZOJ4401 块的计数
- BZOJ3198 [SDOI2013]spring
- BZOJ2839 集合计数
- BZOJ1042 [HAOI2008]硬币购物
- BZOJ2986 Non-Squarefree Numbers
- BZOJ3622 已经没有什么好害怕的了
- BZOJ2669 [CQOI2012]局部极小值
- BZOJ4361 isn
- BZOJ2655 calc
- BZOJ3093 [Fdu校赛2012]A Famous Game
- BZOJ3270 博物馆
- UOJ241 破坏发射台
- hihoCoder1454 Rikka with Tree II
- BZOJ4001 [TJOI2015]概率论
- BZOJ4306 [HAOI2015]按位或