[ABC367C] Enumerate Sequences 题解

[ABC367C] Enumerate Sequences

搜索。

考虑使用 DFS 深搜，对于第 $i$ 个数，从 $1$ 到 $r_i$ 枚举，将 $a_i$ 设为当前枚举的数，并进行下一层递归。

对所有的数填完后，判断当前和是否为 $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); // 下一层递归}
}