Power Table
(modint/power-table.hpp)

• View this file on GitHub
• Last update: 2025-10-21 21:13:36+09:00
• Include: #include "modint/power-table.hpp"

Depends on

• LPF Table (math/lpf-table.hpp)

Verified with

• verify/fps/LC_sum_of_exponential_times_polynomial.test.cpp
• verify/fps/LC_sum_of_exponential_times_polynomial_limit.test.cpp

Code

#pragma once
#include "math/lpf-table.hpp"

// 0^k,1^k,2^k,...,n^k
template <class T>
vector<T> PowerTable(int n, int k) {
  assert(k >= 0);
  vector<T> f;
  if (k == 0) {
    f = vector<T>(n + 1, 0);
    f[0] = 1;
  } else {
    f = vector<T>(n + 1, 1);
    f[0] = 0;
    auto lpf = LPFTable(n);
    for (int i = 2; i <= n; i++)
      f[i] = lpf[i] == i ? T(i).pow(k) : f[i / lpf[i]] * f[lpf[i]];
  }
  return f;
}
/**
 * @brief Power Table
 */

#line 2 "math/lpf-table.hpp"

vector<int> LPFTable(int n) {
  vector<int> lpf(n + 1, 0);
  iota(lpf.begin(), lpf.end(), 0);
  for (int p = 2; p * p <= n; p += (p & 1) + 1) {
    if (lpf[p] != p) continue;
    for (int i = p * p; i <= n; i += p)
      if (lpf[i] == i) lpf[i] = p;
  }
  return lpf;
}
/**
 * @brief LPF Table
 */
#line 3 "modint/power-table.hpp"

// 0^k,1^k,2^k,...,n^k
template <class T>
vector<T> PowerTable(int n, int k) {
  assert(k >= 0);
  vector<T> f;
  if (k == 0) {
    f = vector<T>(n + 1, 0);
    f[0] = 1;
  } else {
    f = vector<T>(n + 1, 1);
    f[0] = 0;
    auto lpf = LPFTable(n);
    for (int i = 2; i <= n; i++)
      f[i] = lpf[i] == i ? T(i).pow(k) : f[i / lpf[i]] * f[lpf[i]];
  }
  return f;
}
/**
 * @brief Power Table
 */

Back to top page