blob: 3ae29c11e58560f4ae93a50409926f8ab9cf4a14 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
#pragma once
#include "poly_div.h"
template <typename Poly> struct PolyLog : public PolyOp<Poly, PolyLog> {
using Base = PolyOp<Poly, PolyLog>;
SHOKA_HELPER_USING_POLY_OP;
explicit PolyLog() : inv{Mod{0}, Mod{1}}, div{} {}
Poly operator()(const Poly &f) { return Base::template single<4>(f); }
void _(int n, Mod *out, const Mod *f) {
if (f[0].get() != 1) {
throw std::invalid_argument("[x^0] f != 1");
}
Poly::assert_power_of_two(n);
Poly::reserve(n);
// log f = \int f' / f
const auto d_f = Poly::template raw_buffer<3>();
d_f[n - 1] = Mod{0};
for (int i = 1; i < n; ++i) {
d_f[i - 1] = Mod{i} * f[i];
}
div._(n, out, d_f, f);
for (int i = n; i-- > 1;) {
out[i] = out[i - 1] * cached_inv(i);
}
out[0] = Mod{0};
}
Mod cached_inv(int n) {
if (static_cast<int>(inv.size()) <= n) {
int old_size = inv.size();
inv.resize(n + 1);
for (int i = old_size; i <= n; ++i) {
inv[i] = -Mod{Mod::mod() / i} * inv[Mod::mod() % i];
}
}
return inv[n];
}
private:
PolyDiv<Poly> div;
std::vector<Mod> inv;
};
|
