官方题解

【算法分析】

设置二维数组 $f$，$f[i][j]$ 表示将 $i$ 个数划分为 $j$ 个子集的划分数。

当 $i == j$ 或者 $j == 1$ 时，划分的方案数为 $1$。

其他情况：
$f[i][j]$ 可以由两个部分得来：
(1) 相比于 $f[i-1][j-1]$，$f[i][j]$ 多出的 $i$ 可以单独作为一个子集，有 $f[i-1][j-1]$ 种方法
(2) 相比于 $f[i-1][j]$，$f[i][j]$ 多出的 $i$ 可以放入划分的 $j$ 个子集中的一个，有 $f[i-1][j] * j$ 种方法

所以 $f[i][j] = (f[i-1][j]*j+f[i-1][j-1])$%$10007$

【参考代码】

#include <iostream>
using namespace std;

int f[110][110];

int main() {
	int n, r;
	cin >> n >> r;
	for (int i = 1; i <= n; i++) {
		f[i][i] = f[i][1] = 1;
	}
	for (int i = 2; i <= n; i++) {
		for (int j = 1; j <= r; j++) {
			f[i][j] = (f[i - 1][j] * j + f[i - 1][j - 1]) % 10007;
		}
	}
	cout << f[n][r];
}

【时间复杂度】

$O(nr)$

【预计得分】

$100pts$