LeetCode-Solutions/C++/count-sequences-to-k.cpp at master · kamyu104/LeetCode-Solutions · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
// Time:  O(3^(n/2))
// Space: O(3^(n/2))

// dp, meet in the middle
class Solution {
private:
    struct TupleHash {
        template <typename... T>
        std::size_t operator()(const std::tuple<T...>& t) const {
            return apply([](const auto&... args) {
                std::size_t seed = 0;
                ((seed ^= std::hash<std::decay_t<decltype(args)>>{}(args) +
                        0x9e3779b9 + (seed << 6) + (seed >> 2)), ...);
                return seed;
            }, t);
        }
    };

public:
    int countSequences(vector<int>& nums, long long k) {
        static const unordered_map<int, tuple<int, int, int>> LOOKUP = {
            {1, {0, 0, 0}},
            {2, {1, 0, 0}},
            {3, {0, 1, 0}},
            {4, {2, 0, 0}},
            {5, {0, 0, 1}},
            {6, {1, 1, 0}}
        };

        const auto& factors = [](int64_t x) {
            int cnt2 = 0;
            while (x % 2 == 0) {
                x /= 2;
                ++cnt2;
            }
            int cnt3 = 0;
            while (x % 3 == 0) {
                x /= 3;
                ++cnt3;
            }
            int cnt5 = 0;
            while (x % 5 == 0) {
                x /= 5;
                ++cnt5;
            }
            return x == 1 ? tuple(cnt2, cnt3, cnt5) : tuple(-1, -1, -1);
        };

        const auto& count = [](const auto& nums) {
            unordered_map<tuple<int, int, int>, int, TupleHash> dp;
            dp[{0, 0, 0}] = 1;
            for (const auto& x : nums) {
                unordered_map<tuple<int, int, int>, int, TupleHash> new_dp;
                const auto& [d2, d3, d5] = LOOKUP.at(x);
                for (const auto& [k, c] : dp) {
                    const auto& [c2, c3, c5] = k;
                    new_dp[{c2, c3, c5}] += c;
                    new_dp[{c2 + d2, c3 + d3, c5 + d5}] += c;
                    new_dp[{c2 - d2, c3 - d3, c5 - d5}] += c;
                }
                dp = move(new_dp);
            }
            return dp;
        };

        const auto& [c2, c3, c5] = factors(k);
        if (c2 == -1) {
            return 0;
        }
        auto left = count(vector<int>(cbegin(nums), cbegin(nums) + (size(nums) / 2)));
        auto right = count(vector<int>(cbegin(nums) + (size(nums) / 2), cend(nums)));
        int result = 0;
        for (const auto& [k, d] : left) {
            const auto& [d2, d3, d5] = k;
            result += d * right[{c2 - d2, c3 - d3, c5 - d5}];
        }
        return result;
    }
};

// Time:  O(3^n)
// Space: O(3^n)
// dp
class Solution2 {
private:
    struct TupleHash {
        template <typename... T>
        std::size_t operator()(const std::tuple<T...>& t) const {
            return apply([](const auto&... args) {
                std::size_t seed = 0;
                ((seed ^= std::hash<std::decay_t<decltype(args)>>{}(args) +
                        0x9e3779b9 + (seed << 6) + (seed >> 2)), ...);
                return seed;
            }, t);
        }
    };

public:
    int countSequences(vector<int>& nums, long long k) {
        static const unordered_map<int, tuple<int, int, int>> LOOKUP = {
            {1, {0, 0, 0}},
            {2, {1, 0, 0}},
            {3, {0, 1, 0}},
            {4, {2, 0, 0}},
            {5, {0, 0, 1}},
            {6, {1, 1, 0}}
        };

        const auto& factors = [](int64_t x) {
            int cnt2 = 0;
            while (x % 2 == 0) {
                x /= 2;
                ++cnt2;
            }
            int cnt3 = 0;
            while (x % 3 == 0) {
                x /= 3;
                ++cnt3;
            }
            int cnt5 = 0;
            while (x % 5 == 0) {
                x /= 5;
                ++cnt5;
            }
            return x == 1 ? tuple(cnt2, cnt3, cnt5) : tuple(-1, -1, -1);
        };

        const auto& count = [](const auto& nums) {
            unordered_map<tuple<int, int, int>, int, TupleHash> dp;
            dp[{0, 0, 0}] = 1;
            for (const auto& x : nums) {
                unordered_map<tuple<int, int, int>, int, TupleHash> new_dp;
                const auto& [d2, d3, d5] = LOOKUP.at(x);
                for (const auto& [k, c] : dp) {
                    const auto& [c2, c3, c5] = k;
                    new_dp[{c2, c3, c5}] += c;
                    new_dp[{c2 + d2, c3 + d3, c5 + d5}] += c;
                    new_dp[{c2 - d2, c3 - d3, c5 - d5}] += c;
                }
                dp = move(new_dp);
            }
            return dp;
        };

        const auto& [c2, c3, c5] = factors(k);
        if (c2 == -1) {
            return 0;
        }
        auto dp = count(nums);
        return dp[{c2, c3, c5}];
    }
};