mod/powertable.hpp

• View this file on GitHub
• Last update: 2023-08-06 03:59:07+09:00
• Include: #include "mod/powertable.hpp"

Depends on

• nt/primetable.hpp

Required by

• graph/count/count_labeled_biconnected.hpp
• graph/count/count_labeled_bridgeless.hpp
• linalg/det_A_plus_xB.hpp
• poly/composition.hpp
• poly/composition_f_1_minus_ex.hpp
• poly/composition_f_a_plus_bx.hpp
• poly/composition_f_a_plus_bx_div_c_plus_dx.hpp
• poly/composition_f_ex_minus_1.hpp
• poly/composition_f_log_1_minus_x.hpp
• poly/compositional_inverse.hpp
• poly/poly_taylor_shift.hpp
• seq/famous/eulerian_number.hpp
• seq/famous/stirling_number_1.hpp
• seq/famous/stirling_number_2.hpp
• seq/famous/surjection.hpp

Verified with

• test/library_checker/math/stirling_number_of_the_first_kind.test.cpp
• test/library_checker/math/stirling_number_of_the_first_kind_fixed_k.test.cpp
• test/library_checker/math/stirling_number_of_the_second_kind.test.cpp
• test/library_checker/math/sum_of_exp_times_poly.test.cpp
• test/library_checker/math/sum_of_exp_times_poly_limit.test.cpp
• test/library_checker/polynomial/composition_of_fps.test.cpp
• test/library_checker/polynomial/compositional_inverse.test.cpp
• test/library_checker/polynomial/polynomial_taylor_shift.test.cpp
• test/mytest/bell.test.cpp
• test/mytest/composition_1_minus_ex.test.cpp
• test/mytest/composition_ex_minus_1.test.cpp
• test/mytest/composition_log_1_minus_x.test.cpp
• test/mytest/compositional_inverset.test.cpp
• test/mytest/count_labeled_biconnected.test.cpp
• test/mytest/count_labeled_bridgeless.test.cpp
• test/mytest/eulerian_number.test.cpp
• test/yukicoder/1303.test.cpp
• test/yukicoder/1321.test.cpp
• test/yukicoder/1392.test.cpp
• test/yukicoder/1760.test.cpp
• test/yukicoder/1821.test.cpp
• test/yukicoder/1875.test.cpp
• test/yukicoder/1907.test.cpp
• test/yukicoder/2005.test.cpp
• test/yukicoder/2206.test.cpp
• test/yukicoder/2580.test.cpp
• test/yukicoder/2583.test.cpp
• test/yukicoder/2587.test.cpp
• test/yukicoder/2587_2.test.cpp
• test_atcoder/abc202_f.test.cpp
• test_atcoder/abc249_ex.test.cpp
• test_atcoder/abc281g.test.cpp
• test_atcoder/arc133f.test.cpp
• test_atcoder/arc153f.test.cpp

Code

#pragma once
#include "nt/primetable.hpp"


// a^0, ..., a^N

template <typename mint>
vc<mint> powertable_1(mint a, ll N) {
  // table of a^i

  vc<mint> f(N + 1, 1);
  FOR(i, N) f[i + 1] = a * f[i];
  return f;
}

// 0^e, ..., N^e

template <typename mint>
vc<mint> powertable_2(ll e, ll N) {
  auto primes = primetable(N);
  vc<mint> f(N + 1, 1);
  f[0] = mint(0).pow(e);
  for (auto&& p: primes) {
    if (p > N) break;
    mint xp = mint(p).pow(e);
    ll pp = p;
    while (pp <= N) {
      ll i = pp;
      while (i <= N) {
        f[i] *= xp;
        i += pp;
      }
      pp *= p;
    }
  }
  return f;
}

#line 2 "nt/primetable.hpp"

template <typename T = int>
vc<T> primetable(int LIM) {
  ++LIM;
  const int S = 32768;
  static int done = 2;
  static vc<T> primes = {2}, sieve(S + 1);

  if (done < LIM) {
    done = LIM;

    primes = {2}, sieve.assign(S + 1, 0);
    const int R = LIM / 2;
    primes.reserve(int(LIM / log(LIM) * 1.1));
    vc<pair<int, int>> cp;
    for (int i = 3; i <= S; i += 2) {
      if (!sieve[i]) {
        cp.eb(i, i * i / 2);
        for (int j = i * i; j <= S; j += 2 * i) sieve[j] = 1;
      }
    }
    for (int L = 1; L <= R; L += S) {
      array<bool, S> block{};
      for (auto& [p, idx]: cp)
        for (int i = idx; i < S + L; idx = (i += p)) block[i - L] = 1;
      FOR(i, min(S, R - L)) if (!block[i]) primes.eb((L + i) * 2 + 1);
    }
  }
  int k = LB(primes, LIM + 1);
  return {primes.begin(), primes.begin() + k};
}
#line 3 "mod/powertable.hpp"

// a^0, ..., a^N

template <typename mint>
vc<mint> powertable_1(mint a, ll N) {
  // table of a^i

  vc<mint> f(N + 1, 1);
  FOR(i, N) f[i + 1] = a * f[i];
  return f;
}

// 0^e, ..., N^e

template <typename mint>
vc<mint> powertable_2(ll e, ll N) {
  auto primes = primetable(N);
  vc<mint> f(N + 1, 1);
  f[0] = mint(0).pow(e);
  for (auto&& p: primes) {
    if (p > N) break;
    mint xp = mint(p).pow(e);
    ll pp = p;
    while (pp <= N) {
      ll i = pp;
      while (i <= N) {
        f[i] *= xp;
        i += pp;
      }
      pp *= p;
    }
  }
  return f;
}

Back to top page