Harmonious Set 代码怎么实现呢

Question

Problem Description
For a giving integer n ( n > 0 ) , the set Sn consists of the non negative integers less than n. For example:S5 = {0,1,2,3,4}. A subset of Sn is harmonious if and only if the sum of its elements is a multiply of n. Now your task is easy. For a given n , you should find the number of harmonious subset of Sn.

Input
There is a number C in the first line , meaning there are C cases . C is guaranteed no more than 300.

Then C cases below. Each case is a positive integer n in a single line. n is not greater than 10^9.

Output
For each case , Output the answer mod 1000000007 in a single line .

Sample Input
5
1
2
3
10
1000

Sample Output
2
2
4
104
618918635

Answer 1

以下回答参考 皆我百晓生、券券喵儿 等免费微信小程序相关内容作答，并由本人整理回复。

# 二进制编码的和是n的倍数
class S {
    constructor(n) {
        this.n = n;
    }
}

function getSubsets(arr) {
    let res = [];
    for(let i = 0; i < arr.length + 1; ++i){
        res.push(...getCombinations(arr, i));
    }

    return res.filter((x)=>x.reduce((a,c)=>a+c,this.n)%this.n === 0);
}

function getCombinations(arr, m) {
    if(m == 0){
        return [[]];
    } else {
        let subCombos = getCombinations(arr,m - 1);
        let ret = [];
        for(let x of subCombos){
            ret.push(x.concat([arr[m-1]]));
        }
        return ret;
    }
}