This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub maspypy/library
#include "mod/powertable.hpp"
#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; }