经典组合问题

在此记录一些经典的组合问题,方便日后查阅。

卡特兰数,斯特林数,放球问题

卡特兰(Catalan )数

$n$ 个0和 $n$个1 组成的序列中始终要保持任意前缀中0的个多不超过1的个数的序列个数为 $\frac{1}{n+1} {2n \choose n }$

这个问题跟括号合理性等一系列问题合理性有关。

$n$ 个0 和 $m$ 个 1 组成的序列($n \leq m$) 保持 任意前缀中 0 的个数不超过1的个数的序列个数为:

把0当$x$-轴,1当$y$-轴,不合理的情况必然经过 $y = x+1$, 在第一次不合理时,后面的路径就开始与 $y = x +1$ 对称,最终结束点为 $(n-1, m+1)$

斯特林(Stirling)数

关于这个问题可以参考这篇博客

第一类斯特林数等到以后用到了再写吧

第二类斯特林数: 将$n$个不同的元素拆分成$m$ 个非空集合的方案数$S(n,m)$。显然有递推关系式:

又我们知道:

将 $n$ 个任意的放在$m$ 个不同盒子中。右边的枚举非空盒子数量$i$,$i$ 个盒子因为是不同的所以要乘$i!$ (不用担心算多了,因为一旦分配好了,盒子本身即使无区别,放了东西就有区别了)
从我的这篇博文 直接可知 (把$n$ 看作常数):

改写成大家通常见到的形式也就是:

补充:知乎上Hongzy写了一篇斯特林数入门 的文章,写的甚好。

正整数分拆数

将正整数$n$拆分成$m$个非负整数之和的方案数$f(n,m)$:

正整数分拆成乘积数

记 $fcnt(n,m)$ 表示 $n$ 的乘法分解都不超过 $m$ 的数

  • 打表时间复杂度 $O(n^{\frac{5}{2})}$,空间复杂度$O(n^2)$ 不推荐!
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<bits/stdc++.h>
using namespace std;
const int N = 10004;
int fcnt[N][N]; //
void initFcnt(){
for(int i=1;i<N;++i) fcnt[1][i] = 1;
for(int i=2;i<N;++i){
int sn = sqrt(i+0.2);
for(int d = 1;d<=sn;++d){
if(i%d) continue;
for(int j = N-1;j>=d;--j) fcnt[i][j]+=fcnt[i/d][d];
for(int j=N-1;j>=i/d;--j) fcnt[i][j]+=fcnt[d][i/d];
}
if(sn*sn == i){
for(int j = N-1;j>=sn;--j) fcnt[i][j]-=fcnt[sn][sn];
}
}
}
int getFcnt(int n){
if(fcnt[1][1] != 1) initFcnt();
return fcnt[n][n];
}

int main(){
int n;
while(cin>>n){
time_t now = time(0);
cout<<getFcnt(n)<<endl;
cout<<"Time used: "<<difftime(time(0),now)<<endl;
}
return 0;
}
  • 递归 (推荐复杂度不好分析)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
using namespace std;

int fcnt(int n,int m){
if(n == 1) return 1;
int sn = sqrt(n+0.2),ans = 0;
for(int d = 1;d<=sn;++d){
if(n%d) continue;
if(d<=m && d>1) ans += fcnt(n/d,d);
if(n/d<=m) ans+= fcnt(d,n/d);
}
if(sn*sn == n && sn<=m) ans-=fcnt(sn,sn);
return ans;
}

int main(){
int n;
while(cin>>n){ // n=98765432109876 = 9.8*10^13 用时 42s, N 大点,耗时会小点
time_t now = time(0);
cout<<fcnt(n,n)<<endl;
cout<<"Time used: "<<difftime(time(0),now)<<endl;
}
return 0;
}

$n$ 个球放在$m$个盒子中

球有相同和不同两种情况,盒子也是,还有盒子能空和不能空,一共八种情况:

  • 球同,盒同,非空

    正整数拆分数之和 $f(n,m) - f(n,m-1) $

  • 球同,盒同,能空

    正整数拆分数$f(n,m)$

  • 球同,盒异,非空

    等价于 $x_1 + \cdots + x_m = n $ 的正整数解,插空法知道$n-1 \choose m-1$

  • 球同,盒异,能空

    同上,$n+m-1 \choose m-1 $

  • 球异,盒同,非空

    第二类斯特林数: $S(n,m)$

  • 球异,盒同,能空

    同上, $\sum_{i=1} ^m S(n,i)$

  • 球异,盒异,非空: $m!S(n,m)$

  • 球异,盒异,能空: $m^n$

有限制的线性方程组的解

$x_1+⋯+x_n=m, c_i < x_i \leq d_i$ 的正整数解的个数 ?

动态规划直接做复杂度 O(m^2 n)

1
2
3
for(int x = d[i];x>c[i];--x){
dp[i][m] += dp[i-1][m-x]
}

不妨设 $c_i = 0,d_i = k$

包容排斥原理做

如有帮助,烦请资瓷(一块也是爱0.0)