c++ simple math multiset while loop
IntuitionApproachApproach Breakdown
1.	Precompute Factorials:
•	It stores factorials up to 16! in the fac array.
•	fac[i] stores i! to help in calculating rank
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->

# Approach
<!-- Describe your approach to solving the problem. -->
Approach Breakdown
	1.	Precompute Factorials:
	•	It stores factorials up to 16! in the fac array.
	•	fac[i] stores i! to help in calculating rank (number of valid permutations before a given choice).
	2.	Use of a Multiset:
	•	ms stores all numbers from 1 to n to allow easy selection and removal while constructing the permutation.
	3.	Greedy Selection of Numbers:
	•	The algorithm builds the permutation one number at a time.
	•	It selects the smallest valid number whose contribution doesn’t exceed the desired k-th permutation count.
	•	The constraints ensure that the sequence maintains the odd-even alternation.
	4.	Counting Valid Permutations Before a Choice:
	•	If selecting a number x at position i would result in fewer than k valid permutations before it, then we skip it.
	•	Otherwise, we choose x and proceed.
	5.	Termination:
	•	The process continues until the permutation is fully constructed.
	1.	Why does fac[(n - siz) / 2] * fac[(n - siz + 1) / 2] work?
	•	The remaining numbers are split into odds and evens.
	•	The number of ways to arrange remaining odds = (remaining_odds)!
	•	The number of ways to arrange remaining evens = (remaining_evens)!
	•	Their product gives the count of valid permutations starting with a given prefix.
	2.	Why cnt is updated?
	•	If skipping a number is safe (i.e., the number of permutations before it is less than k), update cnt and continue.
# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ --> O(n^2)

- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->O(n)

# Code
```cpp []
class Solution {
public:
    vector<int> permute(int n, long long k) {
        /*
            _ fac(right_odd)*fac(right_even)
        */
        vector fac(17, 1ll);
        vector<int> ans;
        for (long long i = 1; i <= 16; ++i)
            fac[i] = fac[i - 1] * i;

        multiset<long long> ms;
        for (long long i = 1; i <= n; ++i)
            ms.insert(i);

        long long cnt = 0;
        while (ms.size()) {
            long long siz = ans.size() + 1;
            if (ans.size() == 0) {

                for (auto& i : ms) {
                    if ((n % 2 && i % 2) || (n % 2 == 0)) {
                        if ((n - siz + 1ll) / 2ll <= 11 &&
                            cnt + fac[(n - siz) / 2] *
                                        fac[((n - siz) + 1ll) / 2ll] <
                                k) {
                            cnt += fac[(n - siz) / 2ll] *
                                   fac[(n - siz + 1ll) / 2ll];
                        } else {
                            ans.push_back(i);
                            break;
                        }
                    }
                }

            } else {
                for (auto& i : ms) {
                    if (i % 2 != ans.back() % 2) {
                        if ((n - siz + 1ll) / 2ll <= 11 &&
                            cnt + fac[(n - siz) / 2] * fac[(n - siz + 1) / 2] <
                                k) {
                            cnt += fac[(n - siz) / 2] * fac[(n - siz + 1) / 2];
                        } else {

                            ans.push_back(i);
                            break;
                        }
                    }
                }
            }
            if (!ans.size())
                break;
            else ms.erase(ans.back());
        }
        return ans;
    }
};
```
['C++']