[ABC367C] Enumerate Sequences
搜索。
考虑使用 DFS 深搜,对于第 i i i 个数,从 1 1 1 到 r i r_i ri 枚举,将 a i a_i ai 设为当前枚举的数,并进行下一层递归。
对所有的数填完后,判断当前和是否为 k k k 的倍数,如果是就输出方案。
void dfs (int x, int sum) {if (x == n + 1) { // 填完了if (sum % k == 0) { // 和是 k 的倍数for (int i = 1; i <= n; i++) cout << a[i] << ' ';cout << '\n';}return ;}for (int i = 1; i <= r[x]; i++) { // 枚举可以填的数a[x] = i;dfs (x + 1, sum + i); // 下一层递归}
}