C - Enumerate Sequences（abc367）

题意：给定n，k和数组r，构造长度为n的整数序列，第i个元素介于1到ri之间，全部元素之和是k的倍数
分析：用dfs遍历每个1到ri之间，层数为n的时间克制深搜
代码：

2. #include<bits/stdc++.h>
3. using namespace std;
4. int n,k,a[100],r[100];
5. void dfs(int i,int sum){
6.         if(i==n){
7.                 if(sum%k==0){
8.                         for(int j=1;j<=n;j++)cout<<a[j]<<" ";
9.                         cout<<endl;
10.                 }
11.                 return;
12.         }
13.         for(int j=1;j<=r[i+1];j++){
14.                 a[i+1]=j;
15.                 dfs(i+1,sum+j);
16.         }
17. }
18. int main(){
19.         cin>>n>>k;
20.         for(int i=1;i<=n;i++)cin>>r[i];
21.         dfs(0,0);
22.         return 0;
23. }

复制代码