From 4fae4bbe35af1eb349623123dc8f7e5f40f772e2 Mon Sep 17 00:00:00 2001 From: mzuenni Date: Sat, 10 Aug 2024 13:43:41 +0200 Subject: more tests --- content/math/transforms/seriesOperations.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'content/math/transforms/seriesOperations.cpp') diff --git a/content/math/transforms/seriesOperations.cpp b/content/math/transforms/seriesOperations.cpp index 4743674..fc36f1e 100644 --- a/content/math/transforms/seriesOperations.cpp +++ b/content/math/transforms/seriesOperations.cpp @@ -4,7 +4,7 @@ vector poly_inv(const vector& a, int n) { vector a2 = a, q2 = q; a2.resize(2*len), q2.resize(2*len); ntt(q2); - for (int j : {0, 1}) { + for (int _ : {0, 1}) { ntt(a2); for (int i = 0; i < 2*len; i++) a2[i] = a2[i]*q2[i] % mod; ntt(a2, true); -- cgit v1.2.3 From 915bbaea690d3d352b06d5a2660166de7fd9cd21 Mon Sep 17 00:00:00 2001 From: mzuenni Date: Sat, 17 Aug 2024 20:07:14 +0200 Subject: improve series operations --- content/math/transforms/seriesOperations.cpp | 14 ++++++++------ tcr.pdf | Bin 691101 -> 691092 bytes 2 files changed, 8 insertions(+), 6 deletions(-) (limited to 'content/math/transforms/seriesOperations.cpp') diff --git a/content/math/transforms/seriesOperations.cpp b/content/math/transforms/seriesOperations.cpp index fc36f1e..b405698 100644 --- a/content/math/transforms/seriesOperations.cpp +++ b/content/math/transforms/seriesOperations.cpp @@ -24,10 +24,13 @@ vector poly_deriv(vector a) { } vector poly_integr(vector a) { - if (a.empty()) return {0}; - a.push_back(a.back() * powMod(sz(a), mod-2, mod) % mod); - for (int i = sz(a)-2; i > 0; i--) - a[i] = a[i-1] * powMod(i, mod-2, mod) % mod; + static vector inv = {0, 1}; + for (static int i = 2; i <= sz(a); i++) + inv.push_back(mod - mod / i * inv[mod % i] % mod); + + a.push_back(0); + for (int i = sz(a) - 1; i > 0; i--) + a[i] = a[i-1] * inv[i] % mod; a[0] = 0; return a; } @@ -35,8 +38,7 @@ vector poly_integr(vector a) { vector poly_log(vector a, int n) { a = mul(poly_deriv(a), poly_inv(a, n)); a.resize(n-1); - a = poly_integr(a); - return a; + return poly_integr(a); } vector poly_exp(vector a, int n) { diff --git a/tcr.pdf b/tcr.pdf index 57691c5..d107dab 100644 Binary files a/tcr.pdf and b/tcr.pdf differ -- cgit v1.2.3