mod/binomial_u64.hpp

• View this file on GitHub
• Last update: 2026-08-30 21:09:36+09:00
• Include: #include "mod/binomial_u64.hpp"

Depends on

• other/bit.hpp

Code

#include "other/bit.hpp"

struct Binomial_u64 {
  int LIM;
  vc<u64> fact, ifact, exp;
  Binomial_u64(int LIM)
      : LIM(LIM), fact(LIM + 1), ifact(LIM + 1), exp(LIM + 1) {
    fact[0] = 1;
    for (int i = 1; i <= LIM; ++i) {
      int k = lowbit(i);
      fact[i] = fact[i - 1] * (i >> k);
      exp[i] = exp[i - 1] + k;
    }
    ifact[LIM] = mod_inv_u64(fact[LIM]);
    for (u64 i = LIM; i >= 1; --i) {
      int k = lowbit(i);
      ifact[i - 1] = ifact[i] * (i >> k);
    }
  }

  u64 C(int n, int k) {
    assert(0 <= n);
    if (k < 0 || n < k) return 0;
    int e = exp[n] - exp[k] - exp[n - k];
    u64 x = fact[n] * ifact[k] * ifact[n - k];
    return x << e;
  }
};

#line 1 "other/bit.hpp"

int popcnt(int x) { return __builtin_popcount(x); }
int popcnt(u32 x) { return __builtin_popcount(x); }
int popcnt(ll x) { return __builtin_popcountll(x); }
int popcnt(u64 x) { return __builtin_popcountll(x); }
int popcnt_sgn(int x) { return (__builtin_parity(unsigned(x)) & 1 ? -1 : 1); }
int popcnt_sgn(u32 x) { return (__builtin_parity(x) & 1 ? -1 : 1); }
int popcnt_sgn(ll x) { return (__builtin_parityll(x) & 1 ? -1 : 1); }
int popcnt_sgn(u64 x) { return (__builtin_parityll(x) & 1 ? -1 : 1); }
// (0, 1, 2, 3, 4) -> (-1, 0, 1, 1, 2)
int topbit(int x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); }
int topbit(u32 x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); }
int topbit(ll x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); }
int topbit(u64 x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); }
// (0, 1, 2, 3, 4) -> (-1, 0, 1, 0, 2)
int lowbit(int x) { return (x == 0 ? -1 : __builtin_ctz(x)); }
int lowbit(u32 x) { return (x == 0 ? -1 : __builtin_ctz(x)); }
int lowbit(ll x) { return (x == 0 ? -1 : __builtin_ctzll(x)); }
int lowbit(u64 x) { return (x == 0 ? -1 : __builtin_ctzll(x)); }

template <typename T>
T kth_bit(int k) {
  assert(0 <= k && k < int(8 * sizeof(T)));
  return T(1) << k;
}
template <typename T>
bool has_kth_bit(T x, int k) {
  assert(0 <= k && k < int(8 * sizeof(T)));
  return x >> k & 1;
}

template <typename UINT>
struct all_bit {
  static_assert(is_unsigned<UINT>::value);
  UINT s;
  all_bit(UINT s) : s(s) {}
  struct iter {
    UINT s;
    int operator*() const { return lowbit(s); }
    void operator++() { s &= s - 1; }
    bool operator!=(nullptr_t) const { return s; }
  };
  iter begin() const { return {s}; }
  nullptr_t end() const { return nullptr; }
};

template <typename UINT>
struct all_subset {
  static_assert(is_unsigned<UINT>::value);
  UINT s;
  all_subset(UINT s) : s(s) {}
  struct iter {
    UINT s, t;
    bool done = false;
    UINT operator*() const { return t; }
    void operator++() {
      done = (t == 0);
      t = (t - 1) & s;
    }
    bool operator!=(nullptr_t) const { return !done; }
  };
  iter begin() const { return {s, s}; }
  nullptr_t end() const { return nullptr; }
};

constexpr u64 full_mask(int n) {
  assert(0 <= n && n <= 64);
  return n == 64 ? -1ULL : (1ULL << n) - 1;
}

u64 bit_reverse(u64 x) {
  x = ((x & 0x5555555555555555ULL) << 1) | ((x >> 1) & 0x5555555555555555ULL);
  x = ((x & 0x3333333333333333ULL) << 2) | ((x >> 2) & 0x3333333333333333ULL);
  x = ((x & 0x0f0f0f0f0f0f0f0fULL) << 4) | ((x >> 4) & 0x0f0f0f0f0f0f0f0fULL);
  x = ((x & 0x00ff00ff00ff00ffULL) << 8) | ((x >> 8) & 0x00ff00ff00ff00ffULL);
  x = ((x & 0x0000ffff0000ffffULL) << 16) | ((x >> 16) & 0x0000ffff0000ffffULL);
  x = (x << 32) | (x >> 32);
  return x;
}
#line 2 "mod/binomial_u64.hpp"

struct Binomial_u64 {
  int LIM;
  vc<u64> fact, ifact, exp;
  Binomial_u64(int LIM)
      : LIM(LIM), fact(LIM + 1), ifact(LIM + 1), exp(LIM + 1) {
    fact[0] = 1;
    for (int i = 1; i <= LIM; ++i) {
      int k = lowbit(i);
      fact[i] = fact[i - 1] * (i >> k);
      exp[i] = exp[i - 1] + k;
    }
    ifact[LIM] = mod_inv_u64(fact[LIM]);
    for (u64 i = LIM; i >= 1; --i) {
      int k = lowbit(i);
      ifact[i - 1] = ifact[i] * (i >> k);
    }
  }

  u64 C(int n, int k) {
    assert(0 <= n);
    if (k < 0 || n < k) return 0;
    int e = exp[n] - exp[k] - exp[n - k];
    u64 x = fact[n] * ifact[k] * ifact[n - k];
    return x << e;
  }
};

Back to top page