[luogu1655][小朋友的球]

luogu1665

思路

一道第二类斯特兰数的模板题。只不过需要写个高精。

f[i][j]表示前i个球放到j个盒子里的方案数。第i个球可以单独一个盒子,所以f[i][j]+=f[i-1][j-1]。还可以与前面的放到同一个盒子里,所以f[i][j]+=f[i-1][j]*j

#include<cstring>
#include<cstdio>
#include<iostream>
using namespace std;
struct BIGNUM {
    int n,a[1000];
    BIGNUM() {
        n=0;
        memset(a,0,sizeof(a));
    }
    BIGNUM(int x) {
        n=0;
        memset(a,0,sizeof(a));
        while(x) {
            a[++n]=x%10;
            x/=10;
        }
    }
    BIGNUM operator * (int x) const{
        BIGNUM c(0);
        c.n=n;
        for(int i=1;i<=c.n;++i)
            c.a[i]=a[i]*x;
        for(int i=1;i<=c.n;++i) {
            if(c.a[i]>=10) {
                c.a[i+1]+=c.a[i]/10;
                c.a[i]%=10;
                if(c.n==i) c.n++;
            }
        }
        return c;
    }
    BIGNUM operator + (const BIGNUM &x) const {
        BIGNUM c(0);
        c.n=max(x.n,n);
        for(int i=1;i<=c.n;++i)
            c.a[i]=x.a[i]+a[i];
        for(int i=1;i<=c.n;++i) {
            if(c.a[i]>=10) {
                c.a[i+1]+=c.a[i]/10;
                c.a[i]%=10;
                if(i==c.n) ++c.n;
            }
        }
        return c;
    }
    void print() {
        for(int i=n;i>=1;--i) printf("%d",a[i]);
        if(n==0)
        puts("0");
        else puts("");
    }
}f[101];
int main() {
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF) {
        f[1]=BIGNUM(1);
        f[0]=BIGNUM(0);
        for(int i=2;i<=m;++i) f[i]=BIGNUM(0);
        for(int i=2;i<=n;++i)
            for(int j=m;j>=1;--j)
                f[j]=f[j-1]+f[j]*j;
        f[m].print();
    }
    return 0;
}

原文地址:https://www.cnblogs.com/wxyww/p/9774436.html

时间: 10-11

[luogu1655][小朋友的球]的相关文章

小朋友的球

题目描述 @发源于 小朋友最近特别喜欢球.有一天他脑子抽了,从口袋里拿出了N个不同的球,想把它们放到M个相同的盒子里,并且要求每个盒子中至少要有一个球,他好奇有几种放法,于是尝试编程实现,但由于他天天不好好学习,只会上B站看游泳教练,于是他向你求助. 输入输出格式 输入格式: 多组数据,每行两个数N,M. 输出格式: 每组数据一行,表示方案数. 输入输出样例 输入样例#1: 4 2 1 1 输出样例#1: 7 1 说明 [样例解释] N=4,M=2 1,2 3 4 2,1 3 4 3,1 2 4

hdu 2208 唉,可爱的小朋友

Problem Description 唉, 小朋友是比较麻烦的.在一个幼儿园里,老师要上一节游戏课,有N个小朋友要玩游戏,做游戏时要用小皮球,但是幼儿园里只有M个小皮球,而且有些小朋友不喜 欢和一些小朋友在一起玩,而只喜欢和另一些小朋友一起玩,比如傻妞只喜欢和傻瓜,傻根,傻蛋们一起玩,傻根又不喜欢和傻蛋一起玩,傻蛋喜欢和傻子一起玩. 所以老师只好把他们分组,每个组至少有一个小球可以玩,而且每个组内不会有两个小朋友,相互不喜欢.现在给你这样一个幼儿园里小朋友之间关系的描述,做为 老师,是否可以上

口袋中球的取出顺序问题,比赛名单问题

对于以下这两种问题是离散数学与概论在编程中的应用: 两个乒乓球队进行比赛,各队人.甲队为A,B,C     乙队为 X,Y,Z    抽签决定比赛名单.有人向队员打听比赛名单,A说他不和X比,C说他不和X,Z比,请编程序找出3组比赛名单 #include<stdio.h> void Game_list() { char i,j,k; /*i是a的对手;j是b的对手;k是c的对手*/ for (i='x';i<='z';i++) for (j='x';j<='z';j++) if (

找球号(一)

找球号(一) 时间限制:3000 ms  |  内存限制:65535 KB 难度:3 描述 在某一国度里流行着一种游戏.游戏规则为:在一堆球中,每个球上都有一个整数编号i(0<=i<=100000000),编号可重复,现在说一个随机整数k(0<=k<=100000100),判断编号为k的球是否在这堆球中(存在为"YES",否则为"NO"),先答出者为胜.现在有一个人想玩玩这个游戏,但他又很懒.他希望你能帮助他取得胜利. 输入 第一行有两个整数

Arcball轨迹球

Arcball屏幕后面的虚拟轨迹球.Arcball的作用是输入屏幕上的点击或拖动,输出轨迹球的旋转量(旋转矩阵或四元数),用来控制摄像机等物体的旋转. https://en.wikibooks.org/wiki/OpenGL_Programming/Modern_OpenGL_Tutorial_Arcball Convert the screen coordinates (in pixels) to camera coordinates (in [-1, 1]) Compute the vect

【网络流24题----04】软件补丁问题魔术球问题

问题描述: 假设有n根柱子,现要按下述规则在这n根柱子中依次放入编号为 1,2,3,4......的球. (1)每次只能在某根柱子的最上面放球. (2)在同一根柱子中,任何2个相邻球的编号之和为完全平方数. 试设计一个算法,计算出在n根柱子上最多能放多少个球.例如,在4 根柱子上最多可放11个球. ´编程任务: 对于给定的n,计算在 n根柱子上最多能放多少个球. ´数据输入: 文件第1 行有 1个正整数n,表示柱子数. ´结果输出: 文件的第一行是球数. 数据规模 n<=60  保证答案小于16

南阳OJ-138 找球号(二)(hash表应用)

找球号(二) 时间限制:1000 ms  |  内存限制:65535 KB 难度:5 描述 在某一国度里流行着一种游戏.游戏规则为:现有一堆球中,每个球上都有一个整数编号i(0<=i<=100000000),编号可重复,还有一个空箱子,现在有两种动作:一种是"ADD",表示向空箱子里放m(0<m<=100)个球,另一种是"QUERY",表示说出M(0<M<=100)个随机整数ki(0<=ki<=100000100),分

仿360加速球。(实现内存释放)

FloatCircleView的实现自定义view 创建WindowManager窗体管理类管理悬浮小球和底部大窗体 MyProgreeView手机底部窗体中小球的实现 FloatMenuView的实现 MyFloatService MainActivity的实现 现在手机上的悬浮窗应用越来越多,对用户来说,最常见的悬浮窗应用就是安全软件的悬浮小控件,拿360卫士来说,当开启悬浮窗时,它是一个小球,小球可以拖动,当点击小球出现大窗体控件,可以进行进一步的操作如:释放手机内存等等.于是借着慕课网的

球的序列(formation.*)

  N个编号为1-n的球,每个球都有唯一的编号.这些球被排成两种序列,分别为A.B序列,现在需要重新寻找一个球的序列l,对于这个子序列l中任意的两个球,要求j,k(j<k),都要求满足lj在A中位置比lk在A中位置靠前,却lj在B中位置比lk在B中位置靠前,请你计算这个子序列l的最大长度. 输入: 第一行一个整数,表示N. 第二行N个整数,表示A序列. 第三行N个整数,表示B序列. 样例输入 5 1 2 4 3 5 5 2 3 4 1 样例输出 2 样例说明 L可以是{2,3},也可以是{2,4

NOIP2013pj小朋友的数字[DP 最大子段和]

描述 有 n 个小朋友排成一列.每个小朋友手上都有一个数字,这个数字可正可负.规定每个小朋友的特征值等于排在他前面(包括他本人)的小朋友中连续若干个(最少有一个)小朋友手上的数字之和的最大值.作为这些小朋友的老师,你需要给每个小朋友一个分数,分数是这样规定的:第一个小朋友的分数是他的特征值,其它小朋友的分数为排在他前面的所有小朋友中(不包括他本人),小朋友分数加上其特征值的最大值.请计算所有小朋友分数的最大值,输出时保持最大值的符号,将其绝对值对 p 取模后输出. 格式 输入格式 第一行包含两个