当前位置 : 主页 > 网页制作 > css >

luogu_P1287 盒子与球

来源:互联网 收集:自由互联 发布时间:2021-06-13
传送门:https://www.luogu.org/problem/P1287 据说这是斯特林数但我并不会QWQ 额....把n个不同球放到m个不同的盒子里,盒子不能为空 一眼排列组合,听取 WA 声一片TAT (什么都别说我太弱了 把

传送门:https://www.luogu.org/problem/P1287

据说这是斯特林数但我并不会QWQ

额....把n个不同球放到m个不同的盒子里,盒子不能为空

一眼排列组合,听取WA声一片TAT(什么都别说我太弱了

把n个不同的球放到m个相同的盒子里,不为空。这种问题是不是可以dp解决?

dp[i][j]=j*dp[i-1][j]+dp[i-1][j-1];

但是我们这里是m个不同的盒子,咋整呢?

最后答案*A(m,m)

因为你在摆放的时候脑补一下那n个球球是不是有顺序的?

既然你盒子没有顺序,你要让他有顺序,能干什么?排列数!

#include<cstdio>
#define R register
using namespace std;
int n,m;
int f[12][12];
inline int jc(int x){
    int y=1;
    for(R int i=2;i<=x;i++)
    y*=i;
    return y;
}
int main (){
    scanf("%d%d",&n,&m);
    f[0][0]=1;
    for(R int i=1;i<=n;i++){
        for(R int j=1;j<=m;j++){
            f[i][j]=j*f[i-1][j]+f[i-1][j-1];
        }
    }
    printf("%d",f[n][m]*jc(m));
    return 0;
}
View Code
上一篇:Sass
下一篇:Codeforces Round #340 (Div. 2)E
网友评论