1 条题解

  • 0
    @ 2025-5-20 16:38:01

    VII.\text{VII}. 球全部相同,盒子全部相同,每个盒子至少装一个球。

    考虑dp计数

    我们设 dpi,jdp_{i,j} 表示将 ii 这个数分成 jj 份,我们考虑拆出来第 jj 个可以是从 j1j-1 个位置新建一个,已经排好的 iji-j 这个数分成 jj 份的每一位同时 +1+1,则有:

    dpi,j=dpij,j+dpi1,j1dp_{i,j}=dp_{i-j,j}+dp_{i-1,j-1}
    int solve7(int n,int m){
    	memset(dp,0,sizeof(dp));
    	for(int i=1;i<=n;i++) dp[i][1]=1;
    	for(int i=1;i<=n;i++){
    		for(int j=2;j<=m;j++){
    			if(i>=j) dp[i][j]+=(dp[i-1][j-1]+dp[i-j][j])%mod;
    		}
    	}
    	return dp[n][m];
    } 
    

    VII.\text{VII}. 球全部相同,盒子全部相同。

    与前面的一样,设出来 mm 个虚假的,然后放即可

    int solve7(int n,int m){
    	memset(dp,0,sizeof(dp));
    	for(int i=1;i<=n+m;i++) dp[i][1]=1;
    	for(int i=1;i<=n+m;i++){
    		for(int j=2;j<=m;j++){
    			if(i>=j) dp[i][j]+=(dp[i-1][j-1]+dp[i-j][j])%mod;
    		}
    	}
    	return dp[n+m][m];
    }
    
    • 1

    信息

    ID
    225
    时间
    1000ms
    内存
    256MiB
    难度
    8
    标签
    (无)
    递交数
    13
    已通过
    7
    上传者