以下是 LeetCode 3154. 到达第 K 级台阶的方案数 的 C++ 实现，附带详细注释：

```cpp
class Solution {
public:
    int waysToReachStair(int k) {
        long long ans = 0;
        
        // 枚举向上跳的次数 a
        // 2^31 已经超过 1e9，所以 a 最大到 31
        for (int a = 0; a <= 31; a++) {
            // 向上跳的总步数：1 + 2 + 4 + ... + 2^(a-1) = 2^a - 1
            long long upSteps = (1LL << a) - 1;
            
            // 当前所在台阶（起始台阶 1，加上所有向上跳的步数）
            long long current = 1 + upSteps;
            
            // 需要的向下跳次数
            long long downSteps = current - k;
            
            // 向下跳次数不能为负数
            if (downSteps < 0) {
                continue;
            }
            
            // 向下跳次数不能超过 a+1（因为 a 次向上跳后有 a+1 个空隙）
            if (downSteps > a + 1) {
                continue;
            }
            
            // 在 a+1 个空隙中选择 downSteps 个位置执行向下跳
            ans += comb(a + 1, (int)downSteps);
        }
        
        return (int)ans;
    }
    
private:
    // 计算组合数 C(n, k)，n 最大为 32
    long long comb(int n, int k) {
        if (k < 0 || k > n) return 0;
        if (k > n - k) k = n - k;
        long long res = 1;
        for (int i = 1; i <= k; i++) {
            res = res * (n - i + 1) / i;
        }
        return res;
    }
};
```

算法思路

核心观察

1. 向上跳的规律：第 i 次向上跳 2^(i-1) 步，所以跳 a 次后总步数为 2^a - 1
2. 最终位置：从台阶 1 出发，跳 a 次后到达 1 + (2^a - 1) = 2^a
3. 向下跳的需求：从 2^a 降到 k，需要向下跳 2^a - k 次

关键约束

· 向下跳次数 down = 2^a - k 必须 ≥ 0
· 不可连续向下跳：在 a 次向上跳形成的 a+1 个间隙中，最多每个间隙放一次向下跳，所以 down ≤ a + 1

计数方法

· 在 a+1 个间隙中选择 down 个位置放下跳
· 方案数 = 组合数 C(a+1, down)

时间复杂度

· O(32 × 32) = O(1)，枚举 a 最多 32 次，每次计算组合数最多 32 步

示例验证

示例 1：k = 0

· a=0: 2^0=1, down=1, C(1,1)=1 ✅
· a=1: 2^1=2, down=2, C(2,2)=1 ✅
· a=2: 2^2=4, down=4, down>3 ❌
· 总计：2 种方案

示例 2：k = 1

· a=0: 2^0=1, down=0, C(1,0)=1 ✅
· a=1: 2^1=2, down=1, C(2,1)=2 ✅
· a=2: 2^2=4, down=3, C(3,3)=1 ✅
· 总计：4 种方案

注意事项

1. 使用 1LL << a 避免整数溢出
2. 组合数计算采用递推公式，直接相乘除，保证精确
3. 最终结果范围在 int 范围内，可以安全转换