1032 - A-B

Time Limit：1s Memory Limit：128MByte

Submissions：528Solved：105

DESCRIPTION
你有n个球，需要把他们放到m个盒子里。要求拥有最多球的盒子唯一，问方案数。
INPUT
一行两个数n、m(n、m≤500)
OUTPUT
一行一个数，表示方案数。答案对998244353取模。
SAMPLE INPUT
5 2
SAMPLE OUTPUT

6

【解题方法1】

dp。

【参考blog】感谢http://blog.csdn.net/yhyyxt/article/details/52549053

dp[i][j]表示i个盒子里面一共放了j个球的情况。

假设球数最多的盒子里面放了k个球，那么剩下的m-1个盒子里面只能放n-k个球，每个盒子最多[0,k-1]个球。

dp[i][j] = ∑dp[i-1][j-x], x∈[0, k]。

用sum[i][j]来求dp[i][j]的前缀和来优化一下。

【AC 代码1】

//
//Created by just_sort 2016/9/25 15:11
//Copyright (c) 2016 just_sort.All Rights Reserved
//

#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll mod = 998244353;
ll dp[505][505];
ll sum[505][505];
int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        dp[0][0] = 1LL;
        for(int i=0; i<=n; i++) sum[0][i] = 1;
        ll ans = 0;
        for(int k=0; k<=n; k++){
            for(int i=1; i<m; i++){
                for(int j=0; j<=n; j++){
                    dp[i][j] = 0;
                    dp[i][j] = (sum[i-1][j] - (j-k>=0 ? sum[i-1][j-k]:0) + mod)%mod;
                    sum[i][j] = ((j==0 ? 0: sum[i][j-1]) + dp[i][j])%mod;
                }
            }
            ans = (ans + m*dp[m-1][n-k])%mod;
        }
        printf("%lld\n",ans);
    }
    return 0;
}

【解题方法2】

组合数学，容斥！

【这个公式有错误】首先ans应该是乘以盒子的数量m,然后里面-的部分应该是*（-1）^k，容斥奇数加偶数减，并且还有一个问题就是n个球放在m个盒子里面，盒子可以为空的方案数的求法，可以参考这篇文章：http://wenku.baidu.com/link?url=snRwVkBTJ0FUvHuU11v_Cmp4BzqUCvuayU27ZSjupARpk_qwn_EyuRpcLamO2pJfDODKpPCaDphlGFkUSvKogeuGPQUD4O-ujDaY24JKEpu

具体公式如下:ps：公式c(n+num-1，n-1)的由来（高中学过的）

将num个相同的红球放到n个盒子里去，每个盒子可以装多个球，也可以不装球，问有多少种放球的方式？

将设每个盒子里面原本就有1个球，将这n个球取出，和num个球混合在一起，那么球的总数就是m=num+n，我们要求的就转化为将m个相同的红球放到n个盒子里的方法有多少种？每个盒子至少有一个球！答案显然就是c(m-1,n-1)

【AC 代码】

//
//Created by just_sort 2016/9/25 15:11
//Copyright (c) 2016 just_sort.All Rights Reserved
//

#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll mod = 998244353;
ll C[1050][1050];
ll work(int x,int y){
    if(x+y-1<0 || y-1<0) return 0;
    return C[x+y-1][y-1];
}

int  main(){
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        C[0][0] = 1;C[1][0] = C[1][1] = 1;
        for(int i=2; i<=1000; i++){
            C[i][0] = 1;
            for(int j=1; j<=1000; j++){
                C[i][j] = (C[i-1][j] + C[i-1][j-1])%mod;
            }
        }
        ll ans = 0;
        for(int x=0; x<=n; x++){
            for(int k=1; k<m; k++){
                ll sum = work(n-x*(k+1),m-1);
                ans = (ans + (k%2==1?1:-1)*C[m-1][k]*sum%mod)%mod;
                ans = (ans + mod)%mod;
            }
        }
        ans = (work(n,m) - ans + mod)%mod;
        ans = m * ans;
        printf("%lld\n",ans);
    }
    return 0;
}