leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

2597.cpp (616B)

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 };