最近学校老是在搞组合数学，周末的考试考的就是组合数学的经典8题，我把它们形象地称作“组合八怪”。那么今天，我就来给大家看看这八怪的真面目（题解）。话不多说，正文开整！

A

给定N个不同的球，放进M个不同的盒子，盒子允许为空，有多少种方案？
样例输入：1 3 2
样例输出：8

这道题简单，直接上代码：

#include <bits/stdc++.h>
#define mod 1000007
using namespace std;
int main()
{
    int t;
    cin>>t;
    for (int i=1;i<=t;i++)
    {
        int n,m;
        cin>>n>>m;
        long long tmp=1;
        for (int j=1;j<=n;j++)
        {
            tmp*=m;
            tmp%=mod;
        }
        cout<<tmp<<endl;
    }
    return 0;
}

B

给定N个不同的球，放进M个不同的盒子，盒子不允许为空，有多少种方案？
样例输入：1 3 2
样例输出：6

从B开始，我就不把思路打出来了好像我A也没打。。。，大家看看代码来理解吧。上代码

#include<bits/stdc++.h>
#define mod 1000007
#define maxn 1005
using namespace std;
long long n,m,ans;
long long f[maxn+5][maxn+5];
void init()
{
    for (int i=1;i<=1005;i++) 
    {
        f[i][1]=f[i][i]=1;
        for (int j=2;j<i;j++)
        f[i][j]=(f[i-1][j]*j+f[i-1][j-1])%mod;  
    }
}
int main()
{
    init();
    int t;
    scanf("%d",&t);
    while(t--)
    {
        ans=0;
        scanf("%lld%lld",&n,&m);
        ans=f[n][m];
        for (int i=1;i<=m;i++)
        ans=ans*i%mod;
        printf("%lld\n",ans);
    }
    return 0;
}

码风突变

C

给定N个不同的球，放进M个相同的盒子，盒子允许为空，有多少种方案？
样例输入：1 3 2
样例输出：4

#include<bits/stdc++.h>
#define mod 1000007
#define maxn 1000
using namespace std;
long long n,m,ans;
long long f[maxn+5][maxn+5];
void init()
{
    for (long long i=1;i<=maxn;i++)
    {
        f[i][1]=f[i][i]=1;
        for (long long j=2;j<=i-1;j++)
        f[i][j]=((f[i-1][j]*j+f[i-1][j-1])%mod);
    }
}
int main()
{
    init();
    int t;
    cin>>t;
    for (int i=1;i<=t;i++)
    {
        ans=0;
        cin>>n>>m;
        for (long long j=1;j<=m;j++)
        ans+=f[n][j],ans%=mod;
        cout<<ans<<endl;
    }
    return 0;
}

D

给定N个不同的球，放进M个相同的盒子，盒子不允许为空，有多少种方案？
样例输入：1 3 2
样例输出：3

#include<bits/stdc++.h>
#define mod 1000007
#define maxn 2000
using namespace std;
long long n,m,ans;
long long f[maxn+5][maxn+5];
void init()
{
    for (long long i=1;i<=maxn;i++) 
    {
        f[i][1]=f[i][i]=1;
        for (long long j=2;j<=i-1;j++)
        f[i][j]=((f[i-1][j]*j+f[i-1][j-1])%mod);
    }
}

int main()
{
    init();
    int t;
    scanf("%d",&t);
    while(t--)
    {
        ans=0;
        scanf("%lld%lld",&n,&m);
        printf("%lld\n",f[n][m]);
    }
    return 0;
}

E

给定N个相同的球，放进M个不同的盒子，盒子允许为空，有多少种方案？
样例输入：1 3 2
样例输出：4

#include <bits/stdc++.h>
#define mod 1000007
using namespace std;
long long t; 
long long n,m;
long long f[2005][2005];
int main()
{
    for (int i=0;i<=2000;i++)
    {
        f[i][0]=1;
        f[i][i]=1;
    }
    for (int i=1;i<=2000;i++)
    for (int j=1;j<i;j++)
    f[i][j]=f[i-1][j]%mod+f[i-1][j-1]%mod;
    cin>>t;
    for (int i=1;i<=t;i++)
    {
        cin>>n>>m;
        cout<<f[n+m-1][m-1]%mod<<endl;
    }
    return 0;
}

码风再次突变

F

给定N个相同的球，放进M个不同的盒子，盒子不允许为空，有多少种方案？
样例输入：1 3 2
样例输出：2

#include <bits/stdc++.h>
#define mod 1000007
using namespace std;
int t; 
int n,m;
int f[1005][1005];
void outputtest()
{
    for (int i=1;i<=10;i++)
    {
        for (int j=1;j<=i;j++)
        cout<<f[i][j]<<" ";
        cout<<endl;
    }
}
int main()
{
    for (int i=0;i<=1000;i++)
    {
        f[i][0]=1;
        f[i][i]=1;
    }
    for (int i=1;i<=1000;i++)
    for (int j=1;j<i;j++)
    f[i][j]=f[i-1][j]%mod+f[i-1][j-1]%mod;
    cin>>t;
    for (int i=1;i<=t;i++)
    {
        cin>>n>>m;
        cout<<f[n-1][m-1]%mod<<endl;
    }
    return 0;
}

outputtest那个函数可以删除，那是调试函数。

G

给定N个相同的球，放进M个相同的盒子，盒子允许为空，有多少种方案？
样例输入：1 3 2
样例输出：2

#include <bits/stdc++.h>
#define mod 1000007
using namespace std;
long long t; 
long long n,m;
long long f[2005][2005];
void outputtest()
{
    for (int i=1;i<=10;i++)
    {
        for (int j=1;j<=i;j++)
        cout<<f[i][j]<<" ";
        cout<<endl;
    }
}
int main()
{
    for (int i=0;i<=2000;i++)
    for (int j=0;j<=2000;j++)
    {
        if (i==0||j==1) f[i][j]=1;
        else if (j>i) f[i][j]=f[i][i]%mod;
        else f[i][j]=f[i][j-1]%mod+f[i-j][j]%mod;
    }
//    outputtest();
    cin>>t;
    for (int i=1;i<=t;i++)
    {
        cin>>n>>m;
        cout<<f[n][m]%mod<<endl;
    }
    return 0;
}

H

给定N个相同的球，放进M个相同的盒子，盒子不允许为空，有多少种方案？
样例输入：1 3 2
样例输出：1

#include <bits/stdc++.h>
#define mod 1000007
using namespace std;
long long t; 
long long n,m;
long long f[2005][2005];
void outputtest()
{
    for (int i=1;i<=10;i++)
    {
        for (int j=1;j<=i;j++)
        cout<<f[i][j]<<" ";
        cout<<endl;
    }
}
int main()
{
    for (int i=0;i<=2000;i++)
    for (int j=0;j<=2000;j++)
    {
        if (i==0||j==1) f[i][j]=1;
        else if (j>i) f[i][j]=f[i][i]%mod;
        else f[i][j]=f[i][j-1]%mod+f[i-j][j]%mod;
    }
//    outputtest();
    cin>>t;
    for (int i=1;i<=t;i++)
    {
        cin>>n>>m;
        cout<<f[n-m][m]%mod<<endl;
    }
    return 0;
}

    好，本篇【OI】到这里就告一段落了。我是Stephen Zeng，如果有什么写的不好的地方或者你有什么建议或感想，欢迎在评论区畅所欲言。我们下篇文章再见！
拜拜ヾ(?ω?`)o