Explained | Clean Code | 0ms
IntuitionConstruct the k-th lexicographically ordered alternating permutation by calculating how many valid permutations follow each possible choice at each pos
# Intuition
Construct the k-th lexicographically ordered alternating permutation by calculating how many valid permutations follow each possible choice at each position.

# Approach
The algorithm uses a combinatorial approach to build the permutation digit-by-digit:

1. Initialize a linked list-like structure (`nx`) to efficiently track available numbers.
2. For each position in the permutation:
   - Iterate through available numbers in ascending order (for lexicographic ordering)
   - For each number, calculate how many valid alternating permutations would follow
   - If the remaining k is within this count, choose this number and update available numbers
   - Otherwise, subtract this count from k and try the next number

The core insight is in `calculate_follow_combs()`, which computes the number of valid alternating permutations starting with a particular number:
- First, it validates if the number maintains the alternating property:
  - For the first position in odd-length permutations, the first element must be odd
  - For other positions, adjacent elements must have different parity
- Then it counts the remaining valid arrangements by calculating the product of factorials of remaining odd and even numbers (since they must be placed in alternating positions)

The solution handles potential overflow using cached factorial values and upper bounding with infinity when needed.

# Complexity
- Time complexity: **O(n²)**
  - For each of the n positions, we iterate through up to n numbers to find the correct one
  - Each calculation is O(1) due to cached factorials

# Code
```cpp []
#include<ranges>

class Solution {
public:
    vector<int> permute(int n, long long k) {
        fill_fac();

        // Linked list-like structure using a vector
        // nx[i] points to the next available number after i
        vector<int> nx = ::views::iota(1, n + 2) | ::ranges::to<vector>();
        --nx.back(); // Last element points to nothing

        vector<int> res;
        res.reserve(n);

        for (int i = 0; i < n; ++i) {
            for (int prev = 0; prev < n; prev = nx[prev]) { // Iterate through available numbers
                // How many valid permutations follow if we choose nx[prev]
                long long combs = calculate_follow_combs(nx[prev], n, res);
                if (combs >= k) { // k within the range of permutations => choose it
                    res.push_back(nx[prev]);
                    nx[prev] = nx[res.back()];
                    break;
                }
                // Skip permutations that start with this number
                k -= combs;
            }
        }

        if (res.size() < n) // Couldn not build a full permutation
            res.clear();
        return res;
    }

private:
    static constexpr long long kInf = numeric_limits<long long>::max();

    static vector<long long> _fac;

    static void fill_fac() {
        if (_fac.size()) return;
        _fac.assign(2, 1);  // 0! 1! are 1
        while (kInf / _fac.size() > _fac.back()) // While fits long long
            _fac.push_back(_fac.back() * _fac.size());
    }

    static long long fac(int n) { // Factorial or inf
        return n < _fac.size() ? _fac[n] : kInf;
    }

    long long calculate_follow_combs(int v, int n, const vector<int>& res) {
        if (res.empty()) {
            // For odd-length permutations, first element must be odd
            if ((n & 1) && !(v & 1)) return 0;
        } else {
            // Adjacent elements must have different parity
            if ((res.back() & 1) == (v & 1)) return 0;
        }

        n -= res.size() + 1; // Remaining elements to place

        int a = n >> 1;  // Number of remaining odd or even numbers
        int b = n - a;   // Number of remaining numbers of other parity

        // Calculate combinations with overflow protection
        long long bf = fac(b);
        long long af = fac(a);
        return kInf / af > bf ? af * bf : kInf;
    }
};

vector<long long> Solution::_fac;

```
['C++']