题目描述

给定一个正整数 $k$，和 $n$ 个正整数$a_1,a_2,\cdots, a_n$，现在想要从 $a_1,a_2,\cdots, a_n$ 中选出若干个数（也可以一个都不取），使得选出的数之和除以 $k$ 的余数恰好等于 $r$。问有多少种取数的方案？

例如：$k=3$，要从 $1,3,8$ 中选若干数。和除以 $k=3$ 的余数为0的有 $0,3,1+8,1+3+8$ 共 $4$ 种；除 $3$ 余 $1$ 的有 $1,1+3$ 这2种；除 $3$ 余 $2$ 的有 $8,3+8$ 这 $2$ 种。

注意：我们认为一个数都不取也是一种取数方案，此时认为和为 $0$。

对每个余数 $r=0,1,\cdots,k-1$，输出和除以 $k$ 余 $r$ 的取数方法数。

输入格式

第1行，2个正整数 $n,k$

第2行，$n$ 个正整数 $a_1,a_2,\cdots, a_n$

输出格式

输出 $k$ 行，第 $i$ 行输出和除以 $k$ 余数为 $i-1$ 的取数方法数。

60分代码

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;

int n, k, r, a[25], cnt;

void dfs(int step, long long sum){
	if (step > n){
		
		if (sum%k == r){
			cnt++;
		}
		return ;
	}
	dfs(step+1, sum);
	dfs(step+1, sum+a[step]);
}

int main(){
	cin >> n >> k;
	for (int i = 1; i <= n; i++){
		cin >> a[i];
	}
	for (; r < k; r++){
		cnt = 0;
		dfs(1, 0);
		printf("%d\n", cnt);
	}
	return 0;
}