组合数学与计数复习
前言：
自从发现，每次打 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 盒子与球
第二类斯特林数，不要和盒子放球类型搞混了！