盒子与球

Pink__ink · 2022-09-02 07:55:31 · 个人记录

背景

小114514有n个球，他又搞到了m个盒子，于是他......

前置知识

排列：n个中，取出m个元素进行排序，有几种不同方法？（n>=m）

运用乘法原理，我们能知道m个位子放n个数有n!/(n-m)!种方法，记作：A_n^m

组合:n个数中，取出m个元素，不考虑排序。(n>=m)

由于不考虑排序，所以我们要去掉m的全排列个数个，也就是m!个。 所以为A_n^m/m!=n!/m!/(n-m)! 记作：C_n^m

正文

一.球相同，盒不同，无空盒：

Link

小114514有n个相同的球，他又搞到了m个不同的盒子。

于是他想知道：在没有空盒的情况下，有多少种放法呢？

分析：

由于球相同，所以我们只需要考虑怎么放盒子。

有一种方法，叫隔板法，假设第1个球前和第n个球后各有一个隔板，那么每两个隔板之间就是一个盒子，所以便把这道题转换为:

在n-1个缝隙中放m-1个隔板，有几种放法？

通过观察，我们发现这就是求C_{n-1}^{m-1}。

Code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,m,ans;
ll get(ll x){
    ll ans=1;
    for(ll i=1;i<=x;i++){
        ans*=i;
    }
    return ans;
}
int main(){
    scanf("%lld%lld",&n,&m);
    printf("%lld",get(n-1)/get(m-1)/get(n-m));
    return 0;
}

二.球相同 ，盒不同，有空盒:

Link

小114514有n个相同的球，他又搞到了m个不同的盒子。

于是他想知道：在可有空盒的情况下，有多少种放法呢？

分析：

这种类型和第一种差不多，只是多了空盒。那么，我们可以用第一种方法改成有空盒的。

我们可以建m个空球，在有空球的情况下使用隔板法，就会产生空盒，所以我们只需要在第一种的基础上把n+=m。

Code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,m,ans;
ll get(ll x){
    ll ans=1;
    for(ll i=1;i<=x;i++){
        ans*=i;
    }
    return ans;
}
int main(){
    scanf("%lld%lld",&n,&m);
    printf("%lld",get(n+m-1)/get(m-1)/get(n));
    return 0;
}

三.球不同，盒相同，无空盒：

Link

小114514有n个不同的球，他又搞到了m个相同的盒子。

于是他想知道：在没有空盒的情况下，有多少种放法呢？

分析：

这道题是第二类斯特林数的模型。

我们可以定义一个dp[x][y]表示前x个球放y个盒子里的放法。

接着，我们来处理边界。

当x=1或y=1时，由于只有一个球或一个盒子，所以dp[x][y]的方法只有一种。

当x<y时，因为不能有空盒，又因为球不够，所以dp[x][y]的值为0.

这就是边界。

最后，我们来讨论第x个球怎么放。

①它独占空盒。因为盒相同，那么它无论放哪个空盒，都只有唯一一种放法，增加dp[x-1][y-1]种。

②它和别的球共享一个盒子。如果不算它，现在的放法就是dp[x-1][y],而x放在这些盒子中，会增加dp[x-1][y]*y种方法。

所以，dp[x][y]=dp[x-1][y-1]+dp[x-1][y]*y

综上，这种问题我们就解出来了。

Code:

#include<bits/stdc++.h>
using namespace std;
#define MAXN 15
#define ll long long
ll dp[MAXN][MAXN],n,m;
int main(){
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(i<j||j==0){
                break;
            }
            else if(i==1||j==1){
                dp[i][j]=1;
            }
            else{
                dp[i][j]=dp[i-1][j-1]+dp[i-1][j]*j;
            }
        }
    }
    printf("%lld",dp[n][m]);
    return 0;
}

四.球不同，盒相同，有空盒:

Link

小114514有n个不同的球，他又搞到了m个相同的盒子。

于是他想知道：在可有空盒的情况下，有多少种放法呢？

分析：

其实，这种问题和第三种是一样的，当我们算出dp[n][1]+dp[n][2].....+dp[n][m]的值时，有空盒的情况也被算进去了。

比如，dp[n][1]就是有m-1个空盒的情况，依此类推......

Code:

#include<bits/stdc++.h>
using namespace std;
#define MAXN 15
#define ll long long
ll dp[MAXN][MAXN],n,m;
int main(){
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(i<j||j==0){
                break;
            }
            else if(i==1||j==1){
                dp[i][j]=1;
            }
            else{
                dp[i][j]=dp[i-1][j-1]+dp[i-1][j]*j;
            }
        }
    }
    ll ans=0;
    for(int i=1;i<=m;i++){
        ans+=dp[n][i];
    }
    printf("%lld",ans);
    return 0;
}

五.球不同，盒不同，无空盒:

Link

小114514有n个不同的球，他又搞到了m个不同的盒子。

于是他想知道：在没有空盒的情况下，有多少种放法呢？

分析：

这一种和第三种的区别在哪？

第三种是盒相同，而这种是盒不同。

有人就会问了，这有什么用呢？

我既然问了，那肯定有大用啦~

假设，我们m和盒子的排列顺序为：

如果我们把m_1和m_2交换一下位置，则又会产生dp[n][m]种方案。

如果我们得到m的的全排列个数，再用得到的数乘上dp[n][m],那就是答案了。

我们知道，m的全排列个数=A_m^m=m!，那么，这种类型不就解出来了吗？

Code:

#include<bits/stdc++.h>
using namespace std;
#define MAXN 15
#define ll long long
ll dp[MAXN][MAXN],n,m;
ll get(ll x){
    ll ans=1;
    for(int i=1;i<=x;i++){
        ans*=i;
    }
    return ans;
}
int main(){
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(i<j||j==0){
                break;
            }
            else if(i==1||j==1){
                dp[i][j]=1;
            }
            else{
                dp[i][j]=dp[i-1][j-1]+dp[i-1][j]*j;
            }
        }
    }
    printf("%lld",dp[n][m]*get(m));
    return 0;
}

六.球不同，盒不同，有空盒:

Link

小114514有n个不同的球，他又搞到了m个不同的盒子。

于是他想知道：在可有空盒的情况下，有多少种放法呢？

水到爆!

分析：

首先，我们知道每个球都有m种方法，既然有n个球，又没有空盒的限制，那么，总方案数不就是n^m吗？

（养成好习惯，用qkpow）

Code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,m;
ll qkpow(ll x,ll y){
    ll ans=1,base;
    base=x;
    while(y){
        if(y&1){
            ans*=base;
        }
        base*=base;
        y>>=1;
    }
    return ans;
}
int main(){
    scanf("%lld%lld",&n,&m);
    printf("%lld",qkpow(m,n));
    return 0;
}

七.球相同,盒相同,无空盒:

Link

小114514有n个相同的球，他又搞到了m个相同的盒子。

于是他想知道：在无空盒的情况下，有多少种放法呢？

分析：

我们首先设dp[x][y]为前x个球，放y个盒子中。

关于初始化，我们知道：

①x=y时，则刚好每个盒子放一个球，那么只有一种放法，所以dp[x][x]=1

②y=1时，则只有一个盒子，我们只能把所有球放在这个盒子里，所以dp[x][1]=1

所以，我们只需要用一重循环去给dp赋初值。

因为要用y个球去铺平盒子，那么dp[x][y]只能由dp[x-y][?]转换而来。

当放了y个球后，dp[x][y]就等于dp[x-y][1]+dp[x-y][2]......+dp[x-y][y],也就是把剩下x-y个球放在1,2,3......y个盒子里面，求和就可以求出dp[x][y]的值。

于是，我们可以用三重循环i,j,k,(i表示球的个数，j表示h的个数，k枚举dp的第二维),来进行dp。

值得一提的是，注意控制j,k的大小。

Code

#include<bits/stdc++.h>
using namespace std;
#define MAXN 1005
#define mod 12345
#define ll long long
ll dp[MAXN][MAXN],n,m;
int main(){
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++){
        dp[i][1]=dp[i][i]=1;
    }
    for(ll i=1;i<=n;i++){
        for(int j=2;j<=m;j++){
            if(j>i){
                break;
            }
            for(int k=1;k<=j;k++){
                (dp[i][j]+=dp[i-j][k])%=mod;
            }
        }
    }
    printf("%lld",dp[n][m]%mod);
    return 0;
}

这样跑出来太慢了，我们可以用类似于前缀和的方法优化一下：

#include<bits/stdc++.h>
using namespace std;
#define MAXN 1005
#define mod 12345
#define ll long long
ll dp[MAXN][MAXN],n,m;
int main(){
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=m;i++){
        dp[0][i]=1;
    }
    for(int i=1;i<=n-m;i++){
        dp[i][1]=1;
        for(int j=2;j<=m;j++){
            dp[i][j]=dp[i][j-1];
            if(j>i){
                continue;
            }
            (dp[i][j]+=dp[i-j][j])%=mod;
        }
    }
    printf("%lld",dp[n-m][m]);
    return 0;
}

八.球相同，盒相同，有空盒:

Link

小114514有n个相同的球，他又搞到了m个相同的盒子。

于是他想知道：在可有空盒的情况下，有多少种放法呢？

分析：

我们可以借鉴第二种的思路，在第七种的基础上建m个空球，自然会产生空盒了！

Code：

#include<bits/stdc++.h>
using namespace std;
#define MAXN 1005
#define ll long long
ll dp[MAXN][MAXN],n,m;
int main(){
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=m;i++){
        dp[0][i]=1;
    }
    n+=m;
    for(int i=1;i<=n-m;i++){
        dp[i][1]=1;
        for(int j=2;j<=m;j++){
            dp[i][j]=dp[i][j-1];
            if(j>i){
                continue;
            }
            dp[i][j]+=dp[i-j][j];
        }
    }
    printf("%lld",dp[n-m][m]);
    return 0;
}

总结

其实盒子与球看上去类型很多，但最主要的只有第一，三，七这三种，其余的，除了第六种很简单，都可以用举一反三的方法推出来！

撒花~~~