AT_abc367_c [ABC367C] Enumerate Sequences 题解

Snowflake_Fairy · 2024-08-18 12:56:54 · 题解

解题思路

首先注意到数据范围：

所以，我们就可以用 dfs 解决这道题目。

对于第 i 个数，我们从 1\sim R_i 之间选择，保存答案后再考虑第 i + 1 个数。

当 i = n + 1 时，也就是所有数都已经考虑完后，我们再判断这些数的和是不是 K 的倍数即可。

CODE：

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, k;
int a[20], b[20];
void dfs(int step, int sum) {
    if (step == n + 1) {
        if (sum % k == 0) {
            for (int i = 1; i <= n; i++)
                cout << b[i] << ' ';
            cout << endl;
        }
        return;
    }
    for (int i = 1; i <= a[step]; i++)
        b[step] = i, dfs(step + 1, sum + i);
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    dfs(1, 0);
    return 0;
}