数学

hj23308 · 2024-05-05 15:04:56 · 算法·理论

BSGS

(int32) [Extend] baby-step giant-step

namespace BSGS {
  int Mul(int x, int y, int p) {
    return int(1LL * x * y % p);
  }

  int BSGS(int a, int b, int p, int y = 1) {
    a %= p, b %= p;
    std::unordered_map<int, int> h;
    int B = (int) std::ceil(std::sqrt(p)), x = 1;
    for (int i = 1; i <= B; i++)
      x = Mul(a, x, p), h[Mul(b, x, p)] = i;
    for (int i = 1; i <= B; i++)
      if (h.count(y = Mul(x, y, p)))
        return i * B - h[y];
    return -1;
  }

  int ExBSGS(int a, int b, int p) {
    a %= p, b %= p;
    int k = 0, y = 1, d = p > 1;
    for (int i = 0; i < 60; i++) {
      if (d == b) return i;
      d = Mul(a, d, p);
    }
    while ((d = std::gcd(a, p)) != 1) {
      if (b % d) return -1;
      k++, p /= d, b /= d;
      y = Mul(y, a / d, p);
    }
    int res = BSGS(a, b, p, y);
    return ~res ? res + k : -1;
  }
}

BSGS_i64

(int64) [Extend] baby-step giant-step

namespace BSGS {
  long long Mul(long long x, long long y, long long p) {
    return (long long) ((__int128) x * y % p);
  }

  long long BSGS(long long a, long long b, long long p, long long y = 1) {
    a %= p, b %= p;
    std::unordered_map<long long, long long> h;
    long long B = (long long) std::ceil(std::sqrt(p)), x = 1;
    for (long long i = 1; i <= B; i++)
      x = Mul(a, x, p), h[Mul(b, x, p)] = i;
    for (long long i = 1; i <= B; i++)
      if (h.count(y = Mul(x, y, p)))
        return i * B - h[y];
    return -1;
  }

  long long ExBSGS(long long a, long long b, long long p) {
    a %= p, b %= p;
    long long k = 0, y = 1, d = p > 1;
    for (long long i = 0; i < 60; i++) {
      if (d == b) return i;
      d = Mul(a, d, p);
    }
    while ((d = std::gcd(a, p)) != 1) {
      if (b % d) return -1;
      k++, p /= d, b /= d;
      y = Mul(y, a / d, p);
    }
    long long res = BSGS(a, b, p, y);
    return ~res ? res + k : -1;
  }
}

Modulo:Add

Modular addition

template<class Tp>
Tp Add(Tp x) { return x; }

template<class Tp, class ...Tps>
int Add(Tp x, Tps ...y) { return (x + Add(y...)) % pMod; }

template<class Tp, class ...Tps>
void AddC(Tp &x, Tps ...y) { x = Add(x, y...); }

Modulo:Mul

Modular multiplication

template<class Tp>
Tp Mul(Tp x) { return x; }

template<class Tp, class ...Tps>
int Mul(Tp x, Tps ...y) { return int(1LL * x * Mul(y...) % pMod); }

template<class Tp, class ...Tps>
void MulC(Tp &x, Tps ...y) { x = Mul(x, y...); }

Modulo:FastPower

Modular fast exponentiation

int Power(int x, int k) {
  int res = 1;
  k = (k % (pMod - 1) + pMod - 1) % (pMod - 1);
  while (k) {
    if (k & 1) MulC(res, x);
    MulC(x, x), k >>= 1;
  }
  return res;
}

Modulo:Inv

Modular multiplicative inverse

int ExGcd(int a, int b, int &x, int &y) {
  if (!b) return x = 1, y = 0, a;
  int d = ExGcd(b, a % b, y, x);
  return y -= a / b * x, d;
}

int Inv(int x) {
  int ret, t, d = ExGcd(x, pMod, ret, t);
  return d * Add(ret, pMod);
}

Modulo:Combination

Modular combination

int fac[maxN], invFac[maxN];

void InitFac(int n = maxN - 1) {
  fac[0] = 1;
  for (int i = 1; i <= n; i++) fac[i] = Mul(fac[i - 1], i);
  invFac[n] = Inv(fac[n]);
  for (int i = n; i >= 1; i--) invFac[i - 1] = Mul(invFac[i], i);
}

int Combination(int n, int m) {
  return m > n ? 0 : Mul(fac[n], invFac[n - m], invFac[m]);
}

Modulo:All

Modular

template<class Tp>
Tp Add(Tp x) { return x; }

template<class Tp>
Tp Mul(Tp x) { return x; }

template<class Tp, class ...Tps>
int Add(Tp x, Tps ...y) { return (x + Add(y...)) % pMod; }

template<class Tp, class ...Tps>
int Mul(Tp x, Tps ...y) { return int(1LL * x * Mul(y...) % pMod); }

template<class Tp, class ...Tps>
void AddC(Tp &x, Tps ...y) { x = Add(x, y...); }

template<class Tp, class ...Tps>
void MulC(Tp &x, Tps ...y) { x = Mul(x, y...); }

int Power(int x, int k) {
  int res = 1;
  while (k) {
    if (k & 1) MulC(res, x);
    MulC(x, x), k >>= 1;
  }
  return res;
}

int ExGcd(int a, int b, int &x, int &y) {
  if (!b) return x = 1, y = 0, a;
  int d = ExGcd(b, a % b, y, x);
  return y -= a / b * x, d;
}

int Inv(int x) {
  int ret, t;
  ExGcd(x, pMod, ret, t);
  return Add(ret, pMod);
}

int fac[maxN], invFac[maxN];

void InitFac(int n = maxN - 1) {
  fac[0] = 1;
  for (int i = 1; i <= n; i++) fac[i] = Mul(fac[i - 1], i);
  invFac[n] = Inv(fac[n]);
  for (int i = n; i >= 1; i--) invFac[i - 1] = Mul(invFac[i], i);
}

int Combination(int n, int m) {
  return m > n ? 0 : Mul(fac[n], invFac[n - m], invFac[m]);
}

Stirling2

[n^2] stirling numbers of the second kind

int stir2[maxN][maxN];

void InitStir() {
  stir2[0][0] = 1;
  for (int i = 1; i < maxN; i++)
    for (int j = 1; j < maxN; j++)
      stir2[i][j] = Add(stir2[i - 1][j - 1], Mul(j, stir2[i - 1][j]));
}