基础计数算法
加：
inline int inc(int x,int k){return(x+=k)<mod?x:x-mod;}减：
inline int dec(int x,int k){return(x-=k)>=0?x:x+mod;}乘：
inline int mul(int x,int k){return x*k*1ll%mod;}除（逆元）：
inline int inv(int x){return quick_pow(x,mod-2,mod);}快速幂：
inline int quick_pow(int x,int k,int mod){
int ans=1;
while(k){
if(k&1)ans=ans*x*1ll%mod;
x=x*x*1ll%mod;
}
return ans;
}阶乘逆元：
inline void ny(){
fac[0]=1;
for(int i=1;i<=n;i++)fac[i]=fac[i-1]*i*1ll%mod;
vac[n]=inv(fac[n]);
for(int i=n-1;i>=1;i--)vac[i-1]=vac[i]*i*1ll%mod;
}组合数计算
- $C_n^m=\frac{n!}{m!(n-m)!}$
inline int C(int n,int m){ if(n<0||m<0||n<m)return 0; else return 1ll*fac[n]*vac[m]%mod*vac[n-m]%mod; } - $C_n^m=C_{n-1}^{m-1}+C_{n-1}^m$
for(int i=1;i<=n;i++){ c[i][0]=1; for(int j=1;j<=i;j++)c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod; } - $C_n^m=C_n^{m-1}\times \frac{n-m+1}{m}$
c[0]=1; for(int i=1;i<=n;i++)c[i]=1ll*c[i-1]*(n-i+1)%mod*inv(i)%mod;组合数
组合数恒等式：
$C_n^m=C_n^{n-m}$
$\sum\limits_{i=0}^{\min(n,m,k)}C_n^i\times C_m^{k-i}=C_{n+m}^k$
$\sum\limits_{i=0}^{n} C_n^i=2^n$
$\sum\limits_{i=1}^{n}C_n^i\times i=n\times 2^{n-1}$
$\sum\limits_{i=0}^{n}C_n^i\times i^2=n\times(n-1)\times2^{n-2}+n\times2^{n-1}$
组合数的简单应用：
例1：
给定一张二维棋盘，每次可以向上走或者向右走，求从 $(0,0)$ 走到 $(n,m)$ 的方案数
显然一共要走 $n+m$ 步，考虑从这 $n+m$ 步中选出 $n$ 步向右走，剩下的向上走即可。答案即为 $C(n+m,n)$
例2：
$n$ 个小球，$m$ 种颜色，第 $i$ 种颜色的小球有 $a_i$ 个，排成一排，求方案数（同种颜色的小球之间不可区分）。
我们不妨一种颜色一种颜色地放,每次从前面还没有使用过的空位置中挑选出 $a_i$ 个进行摆放。
可以得到下式:
例3：
$n$ 个数字，每个数字 $>0$，要求和为 $s$，求方案数
考虑把 $s$ 个相同的小球排成一排，两个相邻的小球之间会有一个间隔。
我们要做的就是在这 $s-1$ 个间隔中选出 $n-1$ 个间隔。
插入一块挡板，然后这样这 $s$ 个小球就被划分为了 $n$ 部分，且每个部分至少有一个球。
故答案为 $C(s-1,n-1)$
变式：$n$ 个数字，每个数字 $\geq0$，要求和为 $s$，求方案数。
不妨在开始之前先向每一段挡板间隔中插入一个小球。
这样就变成了 $s+n$ 个小球，插入 $n$ 个挡板的方案数。也就是 $C(s+n-1,n-1)$
改成每个数字 $>x$ 也是同理。
例4：
计算长度为2n的合法的括号序列方案数。
考虑计算不合法的方案数。
一个不符合要求的 01 序列满足以下特征：
必然在某一奇数位置 $2k+1$ 位上首先出现 $k+1$ 个 $0$ 的累计数和 $k$ 个 $1$ 的。
此后的 $2n-2k-1$ 位上有 $n-k$ 个 $1$ 和 $n-k-1$ 个 $0$。
然后我们考虑一种神奇的构造。把后面这些位置的 $0$ 和 $1$ 互换，使之成为 $n-k$ 个 $0$ 和 $n-k-1$ 个 $1$。
而这样我们可以得到一个唯一的确定的序列，这个序列由 $n+1$ 个 $0$ 和 $n-1$ 个 $1$ 组成。
反过来，我们考虑任意一个由 $n+1$ 个 $0$ 和 $n-1$ 个 $1$ 组成的序列。
由于 $0$ 比 $1$ 多，所以一定存在某一奇数位置 $2k+1$ 位上首先出现 $k+1$ 个 $0$ 的累计数和 $k$ 个 $1$。
然后我们再把这个序列后面的所有位置翻转回去，这样得到的序列可以保证一定是一个在我们的定义下的不合法的序列。
因此，根据这种构造，我们可以证明这两个集合形成了双射，这自然就证明了它们的方案数是相同的。
因此，不合法的方案数就是 $C(2n,n-1)$。
故合法方案数是 $C(2n,n)-C(2n,n-1)$，我们称其为卡特兰数。
斯特林数
集合拆分问题
集合 $\left \{ 1,2…..n\right \} $，划分为 $m$ 个非空集合的方案数。
状态 $(i,j)$：表示 $\left\{1,2,…i\right\}$，划分为了 $j$ 个非空集合的方案数。
策略：考虑第 $i+1$ 个数字怎么放。
自己新开一个集合 $(i,j)->(i+1,j+1)$
找原来一个已有集合丢进去 $(i,j)->j*(i+1,j)$ (有j种不同方案)
转移方程即为： $dp[i][j]=dp[i-1][j-1]+j*dp[i-1][j]$
这个玩意有一个专业的名字——第二类斯特林数
$S(n,m)$ 表示把大小为 $n$ 的集合拆成无序的 $m$ 个非空集合的方案数。
由以上推论可得：$S(n,m)=S(n-1,m-1)+m*S(n-1,m)$
斯特林的容斥解法
自然幂转下降幂
划分数
整数拆分问题
一个整数 $n$，求拆分为 $m$ 个无序非负整数的方案数
那么：$dp[n][m]=dp[n][m-1]+dp[n-m][m]$
这个玩意也叫划分数，称为 $p(n,m)$
8种计数问题
$n$ 个小球放到 $m$ 个盘子里
球有无标号？盘有无标号？是否允许有空盘子？
