leetcode

0 class Solution {

1 public:

2 int beautifulSubsets(const vector<int> &nums, const int g) const {

3 const int n = size(nums);

4 vector<map<int, int>> mat(g);

5 int res = 1;

6

7 for (const int n : nums)

8 mat[n % g][n]++;

9 for (const auto &mp : mat) {

10 int p = 0, dp0 = 1, dp1 = 0;

11 for (const auto [k, v] : mp) {

12 const int t = (1 << v) - 1;

13 dp0 += dp1;

14 dp1 = t * (p + g == k ? dp0 - dp1 : dp0);

15 p = k;

16 }

17 res *= dp0 + dp1;

18 }

19

20 return res - 1;

21 }

22 };