fixed_power_table.h


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

#include "binpow.h"
#include "sieve.h"

#include <vector>

template <typename Mod> struct FixedPowerTable : public std::vector<Mod> {
  explicit FixedPowerTable(int n, int k) : std::vector<Mod>(n) {
    (*this)[0] = Mod{0};
    if (1 < n) {
      (*this)[1] = Mod{1};
    }
    PrimeGen primes(n);
    for (int i = 2; i < n; ++i) {
      auto p = primes.min_div(i);
      (*this)[i] = p == i ? binpow(Mod{i}, k) : (*this)[i / p] * (*this)[p];
    }
  }
};