【算法分析】
设置二维数组 fff，f[i][j]f[i][j]f[i][j] 表示将 iii 个数划分为 jjj 个子集的划分数。
当 i==ji == ji==j 或者 j==1j == 1j==1 时，划分的方案数为 111。
其他情况：
f[i][j]f[i][j]f[i][j] 可以由两个部分得来：
(1) 相比于 f[i−1][j−1]f[i-1][j-1]f[i−1][j−1]，f[i][j]f[i][j]f[i][j] 多出的 iii 可以单独作为一个子集，有 f[i−1][j−1]f[i-1][j-1]f[i−1][j−1] 种方法
(2) 相比于 f[i−1][j]f[i-1][j]f[i−1][j]，f[i][j]f[i][j]f[i][j] 多出的 iii 可以放入划分的 jjj 个子集中的一个，有 f[i−1][j]∗jf[i-1][j] * jf[i−1][j]∗j 种方法
所以 f[i][j]=(f[i−1][j]∗j+f[i−1][j−1])f[i][j] = (f[i-1][j]*j+f[i-1][j-1])f[i][j]=(f[i−1][j]∗j+f[i−1][j−1])%100071000710007
【参考代码】
【时间复杂度】
O(nr)O(nr)O(nr)
【预计得分】
100pts100pts100pts
