球和盒子问题 | FFY's Blog

结论

• $F[i][j]=F[i-1][j-1]+j*F[i-1]j$
• $G[i][j]=G[i][j-1]+G[i-j]j$
• 注意各种情况的初始化

1.放苹果

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=20;
int t,n,m;
int f[maxn][maxn];
int main()
{
    scanf("%d",&t);
    for(int i=0;i<=10;i++)f[0][i]=f[i][1]=f[1][i]=1;
    for(int i=1;i<=10;i++)for(int j=2;j<=10;j++)
    {
        f[i][j]=f[i][j-1];
        if(i>=j)f[i][j]+=f[i-j][j];
    }
    while(t--)
    {
        scanf("%d%d",&n,&m);
        printf("%d\n",f[n][m]);
    }
    return 0;
}

2.数的划分

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn=210;
int n,m;
ll f[maxn][maxn];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<=n;i++)f[0][i]=f[1][i]=f[i][1]=1;
    for(int i=2;i<=n;i++)for(int j=1;j<=m;j++)
    {
        f[i][j]=f[i][j-1];
        if(i>=j)f[i][j]+=f[i-j][j];
    }
    printf("%lld\n",f[n-m][m]);
    return 0;
}

6.小朋友的球

//这题要高精
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn=110;
int n,m;
ll f[maxn][maxn];
int main()
{
    f[1][1]=1;
    for(int i=2;i<=100;i++)for(int j=1;j<=100;j++)
    f[i][j]=f[i-1][j-1]+f[i-1][j]*j;
    while(scanf("%d%d",&n,&m)==2)
    {
        printf("%lld\n",f[n][m]);
    }
    return 0;
}

8.盒子和小球

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=20;
int n,m,f[maxn][maxn];
int main()
{
    scanf("%d%d",&n,&m);f[1][1]=m;
    for(int i=2;i<=n;i++)for(int j=1;j<=m;j++)
    f[i][j]=f[i-1][j-1]*(m-j+1)+f[i-1][j]*j;
    printf("%d\n",f[n][m]);
    return 0;
}

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=20;
int n,m,f[maxn][maxn];
int work(int a)
{
    int ans=1;
    for(int i=2;i<=a;i++)
    ans*=i;
    return ans;
}
int main()
{
    scanf("%d%d",&n,&m);f[1][1]=1;
    for(int i=2;i<=n;i++)for(int j=1;j<=m;j++)
    f[i][j]=f[i-1][j-1]+f[i-1][j]*j;
    printf("%d\n",f[n][m]*work(m));
    return 0;
}