令人自闭的组合数学复习
组合数学练习复习
个人感觉：不看题解没思路，看了题解不知所云，亲自推柿子wa上加wa,平均1道题看题解要做1.5h……
排列组合
- 首先，你需要会打线性筛逆元（基础）。
代码如下：
void init(int N){
inv[1]=1;
fac[0]=1;
invfac[0]=1;
for(int i=2;i<=N;i++){
inv[i]=(mod-mod/i)*(inv[mod%i]%mod);
inv[i]%=mod;
}
for(int i=1;i<=N;i++){
fac[i]=fac[i-1]*(i%mod);
fac[i]%=mod;
invfac[i]=invfac[i-1]*inv[i]%mod;
invfac[i]%=mod;
}
}
-
其次，你需要记住简化排列组合的这些定理
二项式定理
一般组合数化简
插板放球法
这些都可以在我排列组合博客中见到 -
最后，你需要知道做这一类题的常用方法：
a. 抽象意义法，如将题目看成放球问题等等（Binomial Coefficient is Fun）。
b. 答案入手法，如题目告诉你答案该怎么计算时，常使用上面的定理化简然后求解（交错序列）。
容斥原理
首先这个东西在开始做题时是不可能想到的，一般涉及dp时才会用到。
然后呢，设计dp又非常困难，因为你要用容斥原理的话，一般会有两个方程式
关键在于重复的分析，这个十分难搞。
说实话，我个人感觉如果真的涉及到容斥原理的话，我干脆放弃把时间留给其他题目，数论也一样。
除非是很简单的板题......