t4 AC

using ll = long long;
ll comb[48][48] = {0};
class Solution {
    ll getc(ll n, ll r) {
        if (n < r) return 0;
        if (r == 0 || n == r) return comb[n][r] = 1;
        if (comb[n][r]) return comb[n][r];
        return comb[n][r] = getc(n - 1, r) + getc(n - 1, r - 1);
    }
public:
    int waysToReachStair(int k) {
        if (k == 0) return 2;
        for (ll i = 32; i >= 0; --i)
            for (ll j = i; j >= 0; --j)
                getc(i, j);
        ll ans = 0;
        for (ll i = 0; i <= 31; ++i) {
            ll tg = k - 1 + i;
            if ((tg & (tg + 1)) == 0) {
                ll blk = __builtin_popcountll(tg) + 1;
                if (blk >= i) {
                    ll d = comb[blk][i];
                    ans += d;
                }
            }
        }
        return int(ans);
    }
};