Advertisement
pb_jiang

t4 AC

May 18th, 2024
735
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.85 KB | None | 0 0
  1. using ll = long long;
  2. ll comb[48][48] = {0};
  3. class Solution {
  4.     ll getc(ll n, ll r) {
  5.         if (n < r) return 0;
  6.         if (r == 0 || n == r) return comb[n][r] = 1;
  7.         if (comb[n][r]) return comb[n][r];
  8.         return comb[n][r] = getc(n - 1, r) + getc(n - 1, r - 1);
  9.     }
  10. public:
  11.     int waysToReachStair(int k) {
  12.         if (k == 0) return 2;
  13.         for (ll i = 32; i >= 0; --i)
  14.             for (ll j = i; j >= 0; --j)
  15.                 getc(i, j);
  16.         ll ans = 0;
  17.         for (ll i = 0; i <= 31; ++i) {
  18.             ll tg = k - 1 + i;
  19.             if ((tg & (tg + 1)) == 0) {            
  20.                 ll blk = __builtin_popcountll(tg) + 1;
  21.                 if (blk >= i) {
  22.                     ll d = comb[blk][i];
  23.                     ans += d;
  24.                 }
  25.             }    
  26.         }
  27.         return int(ans);
  28.     }
  29. };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement