526互联

排列组合学习指南

发布时间 2023-10-16 21:29:02作者: White_Sheep

前置芝士

卡特兰数

性质

组合数求法

递推法

1<=m,n<=1e3、

const int N=2010,P=1e9+7;
int C[N][N];
//预处理
void init(){
  for(int i=0; i<N; i++) C[i][0] = 1;
  for(int i=1; i<N; i++)
    for(int j=1; j<=i; j++)
      C[i][j]=(C[i-1][j]+C[i-1][j-1])%P;  
}

费马小定理(乘法逆元法、快速幂)

若存在整数 a , p 且gcd(a,p)=1,即二者互为质数

模数是质数的情况下可以用费马小定理+快速幂求逆元

1<=m,n<=1e5

\(C_n^m=\frac{n!}{(n-m)m!}\)

$C^{m}_n $= fact[n] * infact[m] * infact[n - m]

const int N=100010, P=1e9+7;
ll f[N], g[N];
//f[i]:n!,g:(n-m)!、m！
ll qpow(ll a, int b){
  ll res = 1;
  while(b){
    if(b & 1) res=res*a%P;
    a = a*a%P;
    b >>= 1;
  }
  return res;
}
void init(){
  f[0] = g[0] = 1;
  for(int i=1; i<N; i++){
    f[i] = f[i-1]*i%P;
    g[i] = g[i-1]*qpow(i,P-2)%P;
  }  
}
ll getC(ll n,ll m){
  return f[n]*g[m]%P*g[n-m]%P;
}

卢卡斯定理

\[\binom nm\equiv\binom{\lfloor\frac nk\rfloor}{\lfloor\frac mk\rfloor}\times\binom{n\mathrm{~mod~}k}{m\mathrm{~mod~}k}\quad\mathrm{(mod~}k) \]

const int N = 100010;
ll f[N], g[N];
ll qpow(ll a, int b, int p){
  ll res = 1;
  while(b){
    if(b & 1) res=res*a%p;
    a = a*a%p;
    b >>= 1;
  }
  return res;
}
void init(int p){
  f[0] = g[0] = 1;
  for(int i=1; i<=p; i++){
    f[i] = f[i-1]*i%p;
    g[i] = g[i-1]*qpow(i,p-2,p)%p;
  }   
}
ll getC(int n, int m, int p){
  return f[n]*g[m]*g[n-m]%p;
}
int lucas(ll n,ll m, int p){
  if(m==0) return 1;
  return lucas(n/p,m/p,p)*getC(n%p,m%p,p)%p;
}
//
void solve(){
//p为模数
 int n, m, p;
 cin>>n>>m>>p;
 init(p);
 cout<<lucas(n+m,n,p)<<endl;
}

#include <iostream>
#include <vector>

using namespace std;

const int N = 5010;

int primes[N],cnt;
bool st[N];
int sum[N];

void get_primes(int n) //分解质因数，先用线性筛预处理出来题目范围内的所有质数
{
    for(int i = 2; i <= n; i ++ )
    {
        if(!st[i]) primes[cnt ++ ] = i;
        for(int j = 0; primes[j] <= n / i; j ++ )
        {
            st[primes[j] * i] = true;
            if(i % primes[j] == 0) break;
        }
    }
}

int get(int n, int p)//分解质因数，求n的阶乘中有多少个质因子p
{
    int res = 0;
    while(n)
    {
        res += n / p;
        n /= p;
    }
    return res;
}

vector<int> mul(vector<int> a, int b)
{
    vector<int> c;
    int t = 0;
    for(int i = 0; i < a.size(); i ++ )
    {
        t += a[i] * b;
        c.push_back(t % 10);
        t /= 10;
    }
    while(t)
    {
        c.push_back(t % 10);
        t /= 10;
    }
    return c;
}

int main()
{
    int a,b;
    cin >> a >> b;
    get_primes(a);

    for(int i = 0; i < cnt; i ++ )
    {
        int p = primes[i];
        sum[i] = get(a, p) - get(a - b, p) - get(b, p);
    }

    vector<int> res;
    res.push_back(1);

    for(int i = 0; i < cnt; i ++ )
        for(int j = 0; j < sum[i]; j ++ )
            res = mul(res, primes[i]);


    for(int i = res.size() - 1; i >= 0; i -- ) printf("%d", res[i]);
    puts("");

    return 0;
}

代码2

 #include<bits/stdc++.h>
 using namespace std;
 const int N=10007;
 int cnt=0;
 int prim[N];
 bool vis[N];
void init(){
for(int i=2;i<=N;i++){
    if(!vis[i]){
        prim[++cnt]=i;
    for(int j=i;j<=N/i;j++){
        vis[i*j]=true;
    }
    }
}
}
 int get(int n,int p){
    int s=0;
    while(n) s+=n/p,n/=p;
    return s;
 }
 int getC(int n,int m,int p){
    return get(n,p)-get(m,p)-get(n-m,p);
 }
 void mul(int C[],int p,int &len){
    int t=0;
    for(int i=0;i<len;i++){
        t+=C[i]*p;
        C[i]=t%10;
        t/=10;
    }
    while(t){
        C[len++]=t%10;
        t/=10;
    }
 }
 int main(){
    init();
    int C[N],len=1;
    C[0]=1;
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=cnt;i++){
        int p=prim[i];
        int s=getC(n,m,p);
        while(s--) mul(C,p,len);
    }
    for(int i=len-1;i>=0;i--){
        cout<<C[i];
    }
    cout<<endl;
    return 0;
 }

高精度+线性筛法

1<=n,m<=5000，没有模p

const int N = 10010;
int prim[N], vis[N], cnt;

void get_prim(int n){ //筛素数
  for(int i = 2; i <= n; i ++){
    if(!vis[i]) prim[cnt++] = i;
    for(int j=0; i*prim[j]<=n; j++){
      vis[i*prim[j]] = 1;
      if(i%prim[j] == 0) break;
    }
  }
}

int get(int n,int p){ //n!中p的个数
  int s = 0;
  while(n) s += n/p, n /= p;
  return s;
}

int getps(int n,int m,int p){//C中p的个数
  return get(n,p)-get(m,p)-get(n-m,p);
}

void mul(int C[],int p,int &len){//高精度
  int t = 0;
  for(int i=0; i<len; i++){
    t += C[i]*p;
    C[i] = t%10;
    t /= 10;
  }
  while(t){
    C[len++] = t%10;
    t /= 10;
  }
}
//
void solve(){
  int n, m;
  cin >> n >> m; 
  get_prim(n);
  int C[N], len=1; C[0]=1;
  for(int i=0; i<cnt; i++){
    int p = prim[i];
    int s = getps(n,m,p);
    while(s--) mul(C,p,len); 
  }
  for(int i=len-1; i>=0; i--) 
    printf("%d", C[i]);
}

第一类斯特林数

定义：将n个物品分成k个非空轮换的方案数，记住\(\left.\left[\begin{matrix}n\\k\end{matrix}\right.\right]\)，称为斯特林轮换数.

轮换：轮换即为环形排列，如\(\begin{aligned}[A,B,C,D]&=[B,C,D,A]=[C,D,A,B]=[D,A,B,C]\end{aligned}\)

n元素的轮换的方案数为\(\left(n-1\right)!\)

公式：\(\begin{bmatrix}n\\k\end{bmatrix}=(n-1)\begin{bmatrix}n-1\\k\end{bmatrix}+\begin{bmatrix}n-1\\k-1\end{bmatrix}\)

意义：放入最后一个物品，新成立方案数为\(\begin{bmatrix}n-1\\k-1\end{bmatrix}\)，放在前面的集合，每个元素可以产生一个方案，第n个人可以坐到之前n-1个人中任意一个人的左边（保证不重不漏）。

【实例细说】

通常用中括号表示，形如\(\left.\left[\begin{matrix}n\\m\end{matrix}\right.\right]\)，表示�n个人坐�m张圆桌（没有空桌）的方案个数，我们也只需要考虑递推式。考虑第n个人单独坐一张桌子或坐到已经有人的桌子上：如果单独坐一张桌子，前面的n−1就要坐m−1张桌子；如果坐到已经有人的桌子上，就先让n−1个人坐m张桌子，第n个人可以坐到之前n−1个人中任意一个人的左边（其实说右边也无所谓，因为人们坐的是圆桌，这样考虑是为了不重不漏地包含所有的情况）

建筑师

在数轴上建 n 个建筑，每个建筑的高度是 1 到 n 之间的一个整数。

不能有两个建筑的高度相同，从最左边（所有建筑都在右边）看能看到 A 个建筑，从最右边（所有建筑都在左边）看能看到 B 个建筑，满足上述所有条件的建筑方案有多少种？

如果建筑 i 的左(右)边没有任何建造比它高，则建筑 i 可以从左(右)边看到。两种方案不同，当且仅当存在某个建筑在两种方案下的高度不同。

【输入描述】

第一行一个整数 T，代表 T 组数据。 接下来T 行，每行三个整数n,A,B。(1≤n≤50000, 1≤A,B≤100, 1≤T≤200000。)

【输出描述】

对于每组数据输出一行答案 \(mod 10^9+7\)。

【解题思路】

1）高度为n的建筑是肯定不会被挡住的，可以把它作为一个分水岭，在它左边的被左边的建筑挡住，在它右边的被右边的建筑挡住。

2）由此我们可以把所有的建筑分成A+B−1个部分，每个部分由这个部分最高的建筑和被他所挡住的建筑组成，高n的建筑单独构成一个部分。

3）我可以把问题看作除了n以外的n−1个建筑放到A+B−2个圆桌上（n独坐一个桌），这时就是一个斯特林数。

4）对于每个圆桌上的建筑，构成了一个圆排列，但由于必须有一个最高的建筑挡住其他的建筑，这个圆排列的起始端就确定了，可以不重不漏地代表一个之前提到的部分。

5）对于每一个这样的部分，我们只需考虑它是放在�n的左边还是右边，因此答案再乘上一个组合数就可以了。

公式：\(\binom{n-1}{A+B-2}*\binom{A+B-2}{A-1}\)

盒子与球模型

1695948241539

第二类斯特林数

定义：将n个物品分成k个非空集合的方案数，记作\(\left.\left\{\begin{matrix}n\\k\end{matrix}\right.\right\}\)，称为斯特林子集数.

公式：\(\left.\left\{\begin{array}{c}n\\k\end{array}\right.\right\}=k\left\{\begin{array}{c}n-1\\k\end{array}\right\}+\left\{\begin{array}{c}n-1\\k-1\end{array}\right\}\)

意义：放入最后一个物品时，若新成立一个集合，方案数为\(\left.\left\{\begin{array}{l}n-1\\k-1\end{array}\right.\right\}\)，若加入原来的集合，方案数为\(\left.k\left\{\begin{gathered}n-1\\k\end{gathered}\right.\right\}\)。

盒子与球(朴素数据量)

现有 r 个互不相同的盒子和 n 个互不相同的球，要将这 n 个球放入 r 个盒子中，且不允许有空盒子。请求出有多少种不同的放法。

两种放法不同当且仅当存在一个球使得该球在两种放法中放入了不同的盒子。

【输入描述】

输入只有一行两个整数，分别代表 n 和 r。（0≤r≤n≤10，且答案小于 \(2^{31}\)）

【输出描述】

输出一行一个整数代表答案。

int f[20][20];
//jc函数求得是r个盒子的全排列数目：因为盒子不同
int jc(int k)
{
    int ans=1;
    for(int i=2;i<=k;i++)
    {
        ans*=i;
    }
    return ans;
}
void solve(){
	int n,k;
	cin>>n>>k;
	f[0][0]=1;//目前最后一个球放置的方案数
	for(int i=1;i<=n;i++)
		for(int j=1;j<=k;j++){
			f[i][j]=j*f[i-1][j]+f[i-1][j-1];
		}
	cout<<f[n][k]*jc(k)<<endl;
}

三只小猪(数据爆炸量)

给定了房子和猪的数目后，将n只小猪安置在m个房间且没有房间空闲的方案数。

【输入描述】

仅有一行，包含两个整数n和m，分别表示小猪的数目和房间数（1≤n≤50，0≤m≤50）。

【输出描述】

仅一个整数，表示将n只小猪安置在m个房间且没有房间空闲的方案数。

const int N = 55;
int S[N][N][100], L[N][N];

void add(int x, int y) {
	L[x][y] = max(L[x - 1][y - 1], L[x - 1][y]);
	for (int i = 0; i < L[x][y]; i++) {
		S[x][y][i] += S[x - 1][y - 1][i] + y * S[x - 1][y][i];
		S[x][y][i + 1] += S[x][y][i] / 10;
		S[x][y][i] %= 10;
	}
	while (S[x][y][L[x][y]]) {
		S[x][y][L[x][y] + 1] += S[x][y][L[x][y]] / 10;
		S[x][y][L[x][y]] %= 10;
		L[x][y]++;
	}
}
void solve() {
	int n, m;
	cin >> n >> m;
	S[0][0][0] = 1; L[0][0] = 1;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= i; j++)
			add(i, j);
	if (!L[n][m]) cout << 0;
	for (int i = L[n][m] - 1; i >= 0; i--)
		cout << S[n][m][i];
}

插板法

k个球分给n个盒子（每个盒子至少要分得一个球）

k 个球之间形成了k−1 个间隙，我们将n−1 个隔板插入间隙中，隔板就将球分为了k 份，符合假设。这样从k−1 个间隙中选出n−1 个插入隔板，即方案数为\(\mathrm{C}_{k-1}^{n-1}\)。

k个球分给n个盒子（盒子可以分不到球）

我们通过一步化归，转换为上面的情况：添加n 个球，使每个盒子至少有一个球。这样分完后只要将每个盒子多拿的一个球收回，便回到原情况了。于是得到方案数\(\mathrm{C}_{k+n-1}^{n-1}\)。

假设有n 个盒子，每个盒子最多能存储存2个种类不同的球（可以不储存球）。有 0和 1这两种球，其中 0有 a 个，1有b个，单独一个 0或 1算一个方案。现要将这些球储存在盒中，0和 1可以不用全部储存 ，一个盒子可以存放任意多个 0和任意多个 1。输出方案数（a,b≤50，n+a≤50，n+b≤50）

inline __int128 read() {
    __int128 x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}
inline void print(__int128 x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x > 9)
        print(x / 10);
    putchar(x % 10 + '0');
}
__int128 C[101][101];
void init(int n) { //杨辉三角求组合数
    for (int i = 0; i <= n; i++) C[i][0] = 1;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= i; ++j)
            C[i][j] = C[i - 1][j] + C[i - 1][j - 1]; //利用性质求组合数
}
void solve() {
    int n, a, b;
    cin >> n >> a >> b;
    __int128 res = 0;
    init(50);
    for (int i = 0; i <= a; i++)
        for (int j = 0; j <= b; j++)
            res += C[n + i - 1][n - 1] * C[n + j - 1][n - 1];
    print(res);
}