by组合计数

由于组合计数水平过低连黄题都切不掉了QWQ，故作此笔记。

1. 组合数的一些公式

• 排列数：

  即从$n$个元素中，选取$m$个元素进行排列（按一定顺序），记作$A_n^m (m \le n)$。
  有计算公式： $A_n^m=\frac{n!}{(n-m)!}$

• 组合数：

  即从$n$个元素中，选取$m$个元素（无顺序），记作$C_n^m (m \le n)$，当然$\begin{pmatrix}n \\ m \\ \end{pmatrix}$也可以。
  有计算公式： $C_n^m=\frac{A_n^m}{A_m^m}=\frac{n!}{m!(n-m)!}$
  大家都会推就不说为什么了。
  当然，这东西公式和性质挺多的，以下是一些性质。

• 对称性：

  因为组合数，选取元素时选择补集是等价的，所以有： $C_n^m=C_n^{n-m}$

• 递推式：

  这个公式其实可以等价于杨辉三角的公式表达，所以有： $C_n^m=C_{n-1}^{m}+C_{n-1}^{m-1}$

• 二项式定理：

  对于表达式$(a+b)^n$，它的展开式与组合数仍脱不开关系，有等式： $(a+b)^n= \sum_{i=0}^{n}\begin{pmatrix}n \\ m \\ \end{pmatrix}a^{i}b^{n-i}$
  令$a=1,b=1$，等式就变成了$\sum_{i=0}^{n}{C_n^i}=2^n$
  令$a=1,b=-1$，等式就变成了$\sum_{i=0}^{n}{(-1)^i}{C_n^i}=0,(n \ne 0)$

• 范德蒙恒等式：

  很高级的名字，可以用来拆解组合数，等式为： $\sum_{i=0}^{k}C_n^iC_m^{k-i}=C_{n+m}^k$
  怎么来的，这里可以用二项式定理证明：
  对于$(1+x)^n(1+x)^m$，将左右式展开再相乘其中$x^k$项的系数为$\sum_{i=0}^{k}C_n^iC_m^{k-i}$,(即左边$x^i$项系数乘以右边$x^{k-i}$项)。
  对于$(1+x)^{n+m}$，直接套用二项式定理，其$x^k$项系数为$C_{n+m}^k$
  注意到$(1+x)^{n+m}=(1+x)^n(1+x)^m$，所以上式得证。
  对了，这东西有个特殊情况：令$n=m$,则有$\sum_{i=0}^{k}C_n^iC_n^{k-i}=C_{2n}^k$

• 多重组合数&多重集的排列：

  这是什么？
  对于一个多重集，$S_k$里面有个$k$种元素，第$i$个元素有$n_i$个（同种元素无顺序），同时满足$\sum_{i=1}^{k}n_i=n$，现在对这个集合进行排列，有多少种方案。
  有公式：
  $\frac{n!}{\prod_{i=1}^{k}n_i!}$
  怎么来的？先不管相同的元素，元素一共有$n$个，所以一共有$n!$个方案，但对于第$i$个元素，内部的$n_i$个元素，它是无序的，所以把内部的$n_i!$个重复的方案除去就行了。

• 容斥原理：

  引入:

  还记得那个初中思维题吗？有三个比赛项目，9人报名了游泳，7人报名了跑步，5人报名了羽毛球，有多少人报名了项目？ 其实还有数据，懒得打了
  其实这题不难，用集合表示就是，$A$为报名游泳的人，$B$为报名跑步的人，$C$为报名羽毛球的人。对着图分析会发现，答案就是：
  $|A \cup B \cup C|=|A|+|B|+|C|-|A \cap B|-|A \cap C|-|B \cap C|+|A\cap B \cap C|$
  这就是容斥。

  基本概念：

  那么对于$n$个比赛项目，我们也可以用类似的方法推导，但在这之前，我们得先引入几个概念。
  全集：$U$，表示满足问题可能出现的所有情况。
  元素：$x$，对于题设下的一种方案。
  性质：$P_i$，元素所要满足的条件，同时设满足$P_i$性质的元素构成集合$S_i$。

• 多重组合数：

2.一些常见问题

• 错排问题

  问题描述：对于一个长度为$n$排列 $p$，我们要求 $p_i\ne i$ 求可行的方案个数。
  
  问题解析：先扔公式，我们定义用$n$个元素时的方案个数为$D_n$ $D_n=(n-1)(D_{n-1}+D_{n-2})$ 怎么来的？用递推就行了。 对于第$n$个元素，有$n-1$个位置选择放。
  那我换掉的那个元素怎么办？分讨！
  对于换掉的元素$k$：
  $(1)$ 将$k$放在位置$n$，那么对于除外的$n-1$个元素，由于$k$放在了位置$n$，所以剩下的元素就是相当于做一个错排，所以这里有$D_{n-2}$中情况。
  $(2)$当元素$k$不放在位置$n$，这时等同于$p_n\ne k$所以这相当于算上$k$的错排，这时有$D_{n-1}$种放法。
  这时候，将$k$的情况加在一起，然后和$n$的情况相乘，递推式就出来了。

• 不相邻排列

  问题描述： 对于$n$个元素，从中选出$k$个不相邻的元素的方案个数。
  问题解析： 因为元素间除了位置全部相等，所以可以将元素分类

  $1.$我选出来的元素,有$k$个；

  $2.$没被选出来的元素，有$n-k$个。

  既然我们只关心选走的是第几个，所以可以利用插板法，一共有$n-k+1$个空位，选择$k$（不可以相邻）个位置放置选出来的元素，可以得出一共有$C_{n-k+1}^k$个方案。

• Prüfer序列

  问题描述：先看看这题。
  问题解析：问题中描述的节点度数，还是太恶心了点，所以有没有一个可以快速计算带标号树种类数的东西。
  有的有的，兄弟有的，Prüfer 序列就可以帮你解决这个问题。
  这东西是什么？
  首先规定有一个节点标号为 $[1,n]$。的无根树，比如这个：
  • 第一步：找到一个编号最小的叶子节点，比如 $1$ 号。
  • 第二步：然后把它删除。
  • 第三步：同时把与它连接的节点放在序列的末尾。
    然后重复下列操作。
    序列的构造就会像是 $\{ 2 \} \to \{2,2\} \to \{2,2,3\} \to \{2,2,3,3 \} \to \{2,2,3,3,2\}$。
    咦？怎么不往下构造了？因为只剩两个节点时，再往下构造其实就没啥意义了。
    好！哪这个东西有什么用呢？这个序列呢，一看就非常有性质，而在OI圈里，一个有性质的东西，那就有操作空间了。
    拿它有什么性质呢？
    $1.$ 每个结点在序列中出现的次数是其度数减 $1$。（没有出现的就是叶结点）
    $2.$ 在构造完 $Prüfer$ 序列后原树中会剩下两个结点，其中一个一定是编号最大的点$n$

• 一类线性不定方程的解组数

  问题描述：对于方程$x_1+x_2+x_3+ \dots +x_k=n$其中$x$为正整数，求解的组数。
  问题解析：问题可以变一下，求$n$个完全相同的元素，将其分为$k$组，保证每组至少有一个元素，一共有多少种分法？
  因为元素完全相同，我们可以将问题抽象化。这其实不就是用$k-1$块板子将$n$个元素隔开吗？（从左到右，$k-1$块板子将元素分成了$k$组，而这就是我们要的那$k$组元素。）
  一共有$n-1$个空位，$k-1$块板子，所以答案就是$C_{n-1}^{k-1}$
  问题扩展：如果$x$为非负整数呢？
  显然，这相当于每组可以没有元素，这时再用上面的方法就不行了。但如果我先给每组都“借”一个元素并放进去，是不是相当于每个$x$此时都一定不为$0$了，这时候，和上面不就相同了吗。 所以答案就是$C_{n+k-1}^{k-1}$
  不难注意到，这个其实就是可重复选择元素的选择公式。
  其实还有一个严谨的方法，令$t_i=x_i+1，（t_i \ge 1）$，再代入方程，得。
  $\sum_{i=1}^{k}x_i= \sum_{i=1}^k(t_i-1)=n$
  $\sum_{i=1}^kt_i=n+k$
  这时，你就会发现这个方程，和一开始的问题不就一样了吗？所以套公式就行了。
  问题再扩展：到这，就完了吗？显然，还可以在普遍一些。我们规定第$i$组至少有$a_i$个元素。这回怎么办？其实观察“问题扩展”中，我们将问题同化的做法，我们也可以将这个问题转化为基础情况。 设$t_i=x_i-a_i$，代入方程得。 $\sum_{i=1}^{k}x_i= \sum_{i=1}^{k}(t_i+a_i)=n$
  $\sum_{i=1}^{k}t_i=n- \sum_{i=1}^{k}(a_i)$
  这时候，观察方程，发现和扩展的问题等价，所以答案为
  $C_{n-\sum a_i-1}^{k-1}$
  其实，将没见过的问题可以尝试利用见过的问题去解释，或者变换为见过的问题，是个不错的方法。

3.一些例题

1.P6475 [NOI Online #2 入门组] 建设城市

• Case1： 当$x \le n < y$ 时,同时假设地标高度为$h$ 。
  此时$x$ 与 $y$ 在“顶峰”的两侧，两座地标将城市分成了4段区间:
  • $[1,x-1]$ 这一段高度范围为 $[1,h]$
  • $[x+1,n]$ 这一段高度范围为 $[h,m]$
  • $[n+1,y-1]$ 这一段高度范围为 $[h,m]$
  • $[y,2n]$ 这一段高度范围为 $[1,h]$
  你会发现在这几个区间内，我们要解决的是一个相同的子问题。即$[l,r]$区间内，元素值域为$[1,h]$ 且元素值具有单调性的的赋值方案数。
  先不管元素的顺序，先取出一个有$r-l+1$ 个元素的集合，这相当于从$h$ 个元素中可重复的选出$r-l+1$ 个元素，这时，你就会发现，每个集合都对应着一个有单调性的方案（就是将这个集合排序），所以，方案数就是： $C_{h+r-l}^h$ 综上，对于一个确定的$h$ ，方案总数就是四段区间的方案相乘（乘法原理）。
• **Case2：**当$x<y \le n$ 或$n < x <y$ 时,同时假设地标高度为$h$。
  此时，$x,y$ 在中心的同一侧，那没有地标的一侧方案数一定，那利用与 Case1一样的方法进行区间划分，在相乘即可。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=3e5+7;
const int mod=998244353;
int fastpow(int x,int n){
	int res=1;
	while(n){
		if(n&1) res=res*x%mod;
		x=x*x%mod,n=(n>>1);
	}
	return res;
}
int inverse(int x) {return fastpow(x,mod-2);}
int fac[N];
void init() {fac[0]=1;for(int i=1;i<N;i++) fac[i]=fac[i-1]*i%mod;}
int C(int n,int m){//C_n^m
	return fac[n]*inverse(fac[m])%mod*inverse(fac[n-m])%mod;
}
int n,m,x,y;
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	init();
	cin>>m>>n>>x>>y;
	int res=0;
	if(x<=n&&n<y){
		for(int i=1;i<=m;i++){
			int a=C(x-1+i-1,x-1)*C(m-i+1+n-x-1,n-x)%mod,b=C(y-1-n+m-i+1-1,y-1-n)*C(2*n-y+i-1,2*n-y)%mod;
			res=res+a*b%mod;
		}
	}else{
		if(x>n&&y>n) x=x-n,y=y-n;
		for(int i=1;i<=m;i++){
			int a=C(x-1+i-1,x-1)*C(n-y+m-i,n-y)%mod;
			res=(res+a)%mod;
		}
		res=res*C(n+m-1,n)%mod;
	}
	cout<<res%mod<<"\n";
	return 0;
}