题解：AT_donuts_live2014_4 サバゲー

题目(洛谷)
题目(AtCoder)
题目(Vjudge)

题目大意

把 $n$ 个人分成 $m$ 组一共有多少种分法？

分析

从数据范围分析：

$2 \le N \le 1000$

可得出我们需要 $O(n^2)$ 以内的算法。考虑动态规划（dp）。

为什么考虑 dp

这道题考虑方案组数，dp 非常适合解决这种问题。又由于本题可以将方案数量叠加推导得出下一层答案，所以非常适合 dp。

总结：这道题可以从前往后推导，所以适合 dp。

怎么做

dp 分 3 大要素：

1. 状态

我们可以考虑设 $dp_{i,j}$ 为将 $i$ 个人分为 $j$ 组的方案数。

2. 向后推导

我们可以推出 $dp_{i,j} = dp_{i-1,j-1}+dp_{i-1,j}\times j$。

为什么呢？$dp_{i-1,j-1}$ 就不用多说了，是上一次的状态，我们要推导过来肯定需要从这里推导。

至于 $dp_{i-1,j}$，就是第 $i$ 个人进来后，可以进入 $1$ 至 $j$ 每一个组。总共就是通过乘法原理：$dp_{i-1,j}+dp_{i-1,j}+\dots+dp_{i-1,j}$（一共 $j$ 个）。

所以，我们得出了结论，$dp_{i,j} = dp_{i-1,j-1}+dp_{i-1,j}\times j$

3. 答案

我们已经在第一步中设置了 $dp_{i,j}$ 的状态了，第 $n$ 个人分成 $m$ 组自然而然就是 $dp_{n,m}$

代码

#include<bits/stdc++.h>
#define int long long
#define mod 1000000007
using namespace std;
int n,m;
int dp[1005][1005];
signed main(){
    cin>>n>>m;
    dp[0][0]=1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            dp[i][j]=(dp[i-1][j-1]+dp[i-1][j]*j)%mod;
        }
    }
    cout<<dp[n][m];
    return 0;
}

TIPS

十年 OI 一场空，不开 longlong 见祖宗。