组合数学与计数复习（二轮加强）

组合数学与计数复习

前言：

自从发现，每次打 codeforces 或者模拟赛，看到“方案数mod 998244353”就直接跳过了，
这一次为了突破此类题，所以专门对其进行复习。

题单：（洛谷）

链接

硬核知识：

加法原理和乘法原理

感觉就是同类的是加和，互不影响的是乘法。
这个东西常常应用在dp的转移上。

容斥原理：

遇到这种“存在某种状态”的方案数，首先考虑的是容斥原理，当然发现转化后计算量差不多就说明没必要这么做了。

球与盒子（将N个相同的元素分到不同集合的方案数,并且都至少有一个）

C(N-1,M-1)

斯特林数（将N个不同的元素分到M个集合或者环的方案数）。

第一类斯特林数：

分为环的那一种，能旋转得到的两个环视作是一样的。
S(n,k)=S(n-1,k-1)+S(n-1,k)*(n-1)。其中S(0,0)=1。

第二类斯特林数：

分为集合的那一种，集合要求无序且不空。
S(n,k)=S(n-1,k-1)+S(n-1,k)*k。其中S(0,0)=0。

卡特兰数

请移步到数论全家桶查看

题单小结：

[HNOI2008] 越狱：

遇到这种“存在某种状态”的方案数，首先考虑的是容斥原理。
答案为所有方案-相邻两房间均为不同宗教的方案数。
所有方案：m的n次方
对于剩下的，考虑dp，第一个有m种选法，第二个m-1,第三个m-1.....
算一位m*qpow( m-1,n-1)

[CSP-S2019] Emiya 家今天的饭

首先看到“过半”就想到了容斥原理。
然后就是利用dp，做到84pts就很不错了。最后能优化dp就尽力优化掉一个n。
这道题难就难在要分析那些状态会影响到最终容斥后的答案。

P1287 盒子与球

第二类斯特林数，不要和盒子放球类型搞混了！