组合计数 - 特殊数列

一、错排

Ex. 1 P4071 排列计数

1. 题面梗概

求有多少种从 $1$ 到 $n$ 的排列 $a$ ，满足序列中恰好有 $m$ 个位置 $i$ ，使得 $a_{i} = i$ 。

多测 $T \leq 5 \times 10^5, n,m \leq 10^6$

2. 逻辑推导

不妨先来考虑 $m = 0$ 的情况，也就是所有数字全部错位的情况。

发现很难直接用组合数表示出本题的答案，因此考虑使用其他方式进行求解。不妨设有 $n$ 个数的时候答案为 $d_{n}$ ，则尝试寻找 $d$ 数组的递推关系。

考虑第 $a_{n}$ 的取值，显然， $a_{n}$ 有 $n - 1$ 种取值，且每种取值等价。不妨设 $a_{n} = 1$ ，那么来考虑 $a_{1}$ 的取值，则有以下两种情况：

$a_{1} = n$ 。在这种情况下， $a_{1}$ 和 $a_{n}$ 是互相对应的关系，可以直接去掉这两个数字，剩下的就是 $2 \to n-1$ 的数字，答案就是 $d_{n-2}$ 。
$a_{1} \neq n$ 。在这种情况下， $a_{1}$ 和 $a_{n}$ 就不是互相对应的关系了，也就是剩下来 $1 \to n-1$ 的数字错排序，答案就是 $d_{n-1}$ 。

所以可以得出 $n$ 个数完全错拍的递推式为： $d_{n} = (n-1)(d_{n-1} + d_{n-2})$ 。

接着我们分析 $m \neq 0$ 的情况，也就是有 $m$ 个数时完全对应的，那么 $n$ 选 $m$ 就是经典的 $C_{n}^{m}$ ，然后剩下的 $n - m$ 个数完全错排，最终答案就是：

C_{n}^{m} \times d_{n-m}

由于询问的次数很多，所以需要预处理出 $d$ 数组的值，而对于组合数，这里可以采用逆元加速。

3. 代码实现

▶

AcCode

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int maxn = 1e6 + 5;
const int mod = 1e9 + 7;

ll qpow( ll a, ll k )
{
    ll res = 1;
    for( ; k; k >>= 1, a = a * a % mod )
        if( k & 1 ) res = res * a % mod;
    return res;
}

ll d[maxn];
ll fac[maxn], inv[maxn];

void init( int N )
{
    d[0] = d[1] = 0, d[2] = 1, d[3] = 2;
    for( int i = 4; i <= N; ++ i ) d[i] = ( i - 1 ) * ( d[i-1] + d[i-2] ) % mod;
    fac[0] = 1;
    for( int i = 1; i <= N; ++ i ) fac[i] = fac[i-1] * i % mod;
    inv[N] = qpow( fac[N], mod - 2 );
    for( int i = N - 1; i >= 0; -- i ) inv[i] = inv[i+1] * ( i + 1 ) % mod;
}

ll get_C( ll n, ll m ) 
{ 
    if( n < m ) return 0;
    return fac[n] * inv[m] % mod * inv[n - m] % mod; 
}

void solve( )
{
    int n, m;
    cin >> n >> m;
    if( n == m ) { cout << 1 << '\n'; return ; }
    cout << ( d[n - m] * get_C( n, m ) % mod ) << '\n';
}

int main( )
{
    ios::sync_with_stdio( 0 ); cin.tie( 0 );
    init( maxn - 5 );
    int _t = 1; cin >> _t;
    while( _t -- ) solve( );
    return 0;
}

二、卡特兰数

Ex. 1 P1044 栈

1. 题意梗概

有一个空栈，有 $n$ 个元素依次按照顺序入栈，但在入栈的过程中可能随时会有元素出栈的情况。求最终合法的出栈顺序方案数。

$n \leq 18$

2. 逻辑推导

不妨设 $C_{n}$ 为元素个数为 $n$ 时的答案，考虑采用递推的方式进行求解。

考虑编号为 $1$ 的元素出栈的位置。容易发现，如果 $1$ 号元素是第 $k$ 个出栈的，那么 $2$ 到 $k$ 的元素在此时必然已经出栈，而后 $n-k$ 个元素在此时还没有进栈。

由于前后两部分的出栈顺序同样满足先入先出的条件，因此编号为 $2$ 到 $k$ 的元素的出栈顺序种类数量为 $C_{k-1}$ 种，而后 $n-k$ 个元素的出栈顺序恰为 $C_{n-k}$ 种。

所以执行需要将 $k$ 取遍 $1 \to n$ 即为最终的答案：

C_{n} = \sum_{k=1}^{n}( C_{k-1} \times C_{n-k} )

也可以写成：

C_{n} = \sum_{i=0}^{n-1} (C_{i} \times C_{n-i-1})

其中 $C_{0} = 1$ ，那么求出 $C_{n}$ 即为答案。

三、斯特林数

Ex.1 P1287 盒子与球

1. 题面梗概

有多少种方案将 $n$ 个互不相同的球放入 $r$ 个互不相同的盒子，使得没有一个盒子为空。

$0 \leq r \leq n \leq 10$

2. 逻辑推导

换一个角度分析，如果所有的盒子都是相同的，本题应该如何处理。

考虑递推，设 $S(n, r)$ 表示有 $n$ 个球 $r$ 个盒子，且盒子相同的答案。不妨将球按 $1$ 到 $n$ 编号，考虑编号为 $n$ 的球的放置情况.

该球独占一个盒子。此时剩下的 $n-1$ 个球应当共享 $r-1$ 个盒子，故方案数为 $S(n-1, r-1)$ 。
该球与其他球共享一个盒子。此时不妨先摆好其他球（ $S(n-1, r)$ 种情况）。接着，由于编号为 $n$ 的球可以放置在 $r$ 个盒子中，故通过乘法原理，方案数为 $r \times S(n-1, r)$ 。