by组合计数

JackZHD · 2025-04-18 17:25:53 · 个人记录

由于组合计数水平过低连黄题都切不掉了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：

  $(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圈里，一个有性质的东西，那就有操作空间了。
  拿它有什么性质呢？

  $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 入门组] 建设城市

题目分析
观察题目，注意到题目中的x,y 两座楼可以在同侧，也可以在异侧，所以要先对大前提分讨。同时注意到值域m \in [1,10^5] 所以可以枚举地标高度。

• 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一样的方法进行区间划分，在相乘即可。

总结： 对于问题，合理的将问题拆解，进行分类讨论或是分步计算，利用计数原理统计计数。

Code

#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;
}