【算法分析】 设置二维数组 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

#include <iostream> #include <vector> // 计算Stirling数（第二类）的函数 int stirlingNumber(int n, int r) { // 创建一个二维数组来存储中间结果 stdvector<stdvector<long long>> dp(n + 1, std::vector<long long>(r + 1, 0)); } int main() { int n, r; std::cin >> n >> r; // 读取输入 }

def count_partitions(n, r): MOD = 10007 dp = [[0] * (r + 1) for _ in range(n + 1)] dp[0][0] = 1 # 初始化，没有元素划分为0个子集的方法只有一种 读取输入 n, r = map(int, input().split()) 计算并输出结果 print(count_partitions(n, r))