dirichlet_series.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include <cstdint> | ||
| 4 | #include <algorithm> | ||
| 5 | #include <cassert> | ||
| 6 | #include <type_traits> | ||
| 7 | #include <array> | ||
| 8 | |||
| 9 | namespace dirichlet_series { | ||
| 10 | |||
| 11 | ✗ | inline int inv(int v) { | |
| 12 | ✗ | assert(v == 1); | |
| 13 | ✗ | return 1; | |
| 14 | } | ||
| 15 | |||
| 16 | 60 | inline int64_t inv(int64_t v) { | |
| 17 | 60 | assert(v == 1); | |
| 18 | 60 | return 1; | |
| 19 | } | ||
| 20 | |||
| 21 | 60175 | constexpr int64_t floor_sqrt(int64_t N) { | |
| 22 | 60175 | assert(N >= 0); | |
| 23 |
1/4✓ Branch 4 → 5 taken 60175 times.
✗ Branch 4 → 6 not taken.
✗ Branch 4 → 9 not taken.
✗ Branch 4 → 11 not taken.
|
60175 | if (N == 0) return 0; |
| 24 | ✗ | int64_t a = N; | |
| 25 | 1015063 | while (true) { | |
| 26 |
1/2✗ Branch 5 → 6 not taken.
✓ Branch 5 → 7 taken 318 times.
|
537619 | int64_t b = N/a; |
| 27 | 537619 | assert(a >= b); | |
| 28 |
4/4✓ Branch 7 → 8 taken 477210 times.
✓ Branch 7 → 9 taken 60091 times.
✓ Branch 9 → 10 taken 234 times.
✓ Branch 9 → 11 taken 84 times.
|
537619 | if (a-b <= 1) return b; |
| 29 | 477444 | a = (a+b+1)>>1; | |
| 30 | 477444 | } | |
| 31 | } | ||
| 32 | |||
| 33 | class div_vector_layout { | ||
| 34 | public: | ||
| 35 | int64_t N; | ||
| 36 | int64_t rt = floor_sqrt(N); | ||
| 37 | int len = int(2 * rt + (rt * (rt+1) <= N)); | ||
| 38 | |||
| 39 | 60175 | constexpr div_vector_layout(int64_t N_ = 1) : N(N_) {} | |
| 40 | |||
| 41 | 4575 | constexpr int get_value_bucket(int64_t a) const { | |
| 42 |
3/6✗ Branch 2 → 3 not taken.
✗ Branch 2 → 4 not taken.
✓ Branch 5 → 6 taken 724 times.
✓ Branch 5 → 7 taken 3803 times.
✗ Branch 9 → 10 not taken.
✓ Branch 9 → 13 taken 3803 times.
|
4575 | return a <= rt ? int(a) : len - int(N/a); |
| 43 | } | ||
| 44 | 32906380 | constexpr int64_t get_bucket_bound(int i) const { | |
| 45 |
5/8None:
✓ Branch 4 → 5 taken 6169142 times.
✓ Branch 4 → 6 taken 6169178 times.
dirichlet_series::div_vector_layout::get_bucket_bound(int) const:
✗ Branch 2 → 3 not taken.
✗ Branch 2 → 4 not taken.
✓ Branch 5 → 6 taken 71208 times.
✓ Branch 5 → 18 taken 72180 times.
✗ Branch 11 → 12 not taken.
✓ Branch 11 → 15 taken 71208 times.
|
32906380 | return i <= rt ? i : N/(len-i); |
| 46 | } | ||
| 47 | }; | ||
| 48 | |||
| 49 | template <const div_vector_layout& layout, typename T> class div_vector { | ||
| 50 | public: | ||
| 51 | // Let's just make everything public, getters and setters are too much work | ||
| 52 | T* st = new T[layout.len+1]{}; // Allocate one extra on each side | ||
| 53 | T* en = st + layout.len; | ||
| 54 | |||
| 55 |
9/12dirichlet_series::div_vector<dirichlet_series::test::layout, modnum<1000000007> >::div_vector():
✓ Branch 4 → 5 taken 11696 times.
✗ Branch 4 → 11 not taken.
✓ Branch 20 → 12 taken 574722 times.
✓ Branch 20 → 21 taken 11696 times.
dirichlet_series::div_vector<dirichlet_series::test::layout, long>::div_vector():
✓ Branch 4 → 5 taken 240 times.
✗ Branch 4 → 11 not taken.
✓ Branch 16 → 12 taken 1960 times.
✓ Branch 16 → 17 taken 240 times.
dirichlet_series::div_vector<main::layout, modnum<998244353> >::div_vector():
✓ Branch 2 → 3 taken 180273 times.
✗ Branch 2 → 5 not taken.
✓ Branch 7 → 6 taken 141416001 times.
✓ Branch 7 → 8 taken 180273 times.
|
142184892 | div_vector() = default; |
| 56 | |||
| 57 | /* Rule of 5 declarations */ | ||
| 58 |
3/4✓ Branch 4 → 5 taken 48 times.
✗ Branch 4 → 11 not taken.
✓ Branch 20 → 12 taken 716 times.
✓ Branch 20 → 21 taken 48 times.
|
764 | div_vector(div_vector const& o) { |
| 59 | 48 | std::copy(o.st, o.en, st); | |
| 60 | 48 | } | |
| 61 | ✗ | div_vector& operator = (div_vector const& o) { | |
| 62 | ✗ | std::copy(o.st, o.en, st); | |
| 63 | ✗ | return *this; | |
| 64 | } | ||
| 65 | 240 | friend void swap(div_vector& a, div_vector& b) { | |
| 66 | 240 | std::swap(a.st, b.st); | |
| 67 | 240 | std::swap(a.en, b.en); | |
| 68 | 240 | } | |
| 69 | 120 | div_vector(div_vector && o) : st(nullptr), en(nullptr) { | |
| 70 | 120 | swap(*this, o); | |
| 71 | 120 | } | |
| 72 | 96 | div_vector& operator = (div_vector && o) { | |
| 73 | 96 | swap(*this, o); | |
| 74 | 96 | return *this; | |
| 75 | } | ||
| 76 |
10/16None:
✓ Branch 15 → 16 taken 48 times.
✗ Branch 15 → 17 not taken.
✓ Branch 17 → 18 taken 48 times.
✗ Branch 17 → 19 not taken.
✓ Branch 19 → 20 taken 30022 times.
✗ Branch 19 → 21 not taken.
✓ Branch 21 → 22 taken 30022 times.
✗ Branch 21 → 23 not taken.
✓ Branch 23 → 24 taken 30021 times.
✗ Branch 23 → 25 not taken.
✓ Branch 25 → 26 taken 30021 times.
✗ Branch 25 → 27 not taken.
dirichlet_series::div_vector<dirichlet_series::test::layout, modnum<1000000007> >::~div_vector():
✓ Branch 4 → 5 taken 11744 times.
✓ Branch 4 → 8 taken 90 times.
dirichlet_series::div_vector<dirichlet_series::test::layout, long>::~div_vector():
✓ Branch 4 → 5 taken 240 times.
✓ Branch 4 → 8 taken 30 times.
|
72195 | ~div_vector() { delete[] st; } |
| 77 | |||
| 78 |
3/3✓ Branch 8 → 9 taken 1 time.
✓ Branch 8 → 10 taken 47 times.
✓ Branch 11 → 12 taken 48 times.
|
1474 | T& operator [] (int64_t v) { return st[layout.get_value_bucket(v)]; } |
| 79 | ✗ | T& operator [] (int64_t v) const { return st[layout.get_value_bucket(v)]; } | |
| 80 | }; | ||
| 81 | |||
| 82 | template <div_vector_layout const& layout, typename T, typename Derived> class vectorspace_mixin { | ||
| 83 | private: | ||
| 84 | ✗ | Derived& underlying() { | |
| 85 | ✗ | return static_cast<Derived&>(*this); | |
| 86 | } | ||
| 87 | ✗ | Derived const& underlying() const { | |
| 88 | ✗ | return static_cast<Derived const&>(*this); | |
| 89 | } | ||
| 90 | |||
| 91 | public: | ||
| 92 | ✗ | friend Derived operator + (Derived&& a) { | |
| 93 | ✗ | for (int64_t i = 1; i < layout.len; i++) { | |
| 94 | ✗ | a.st[i] = +a.st[i]; | |
| 95 | } | ||
| 96 | ✗ | return a; | |
| 97 | } | ||
| 98 | ✗ | friend Derived operator + (Derived const& a) { return +Derived(a); } | |
| 99 | ✗ | friend Derived operator - (Derived && a) { | |
| 100 | ✗ | for (int64_t i = 1; i < layout.len; i++) { | |
| 101 | ✗ | a.st[i] = -a.st[i]; | |
| 102 | } | ||
| 103 | ✗ | return a; | |
| 104 | } | ||
| 105 | ✗ | friend Derived operator - (Derived const& a) { return -Derived(a); } | |
| 106 | |||
| 107 | ✗ | Derived& operator += (Derived const& o) { | |
| 108 | ✗ | for (int64_t i = 1; i < layout.len; i++) { | |
| 109 | ✗ | underlying().st[i] += o.st[i]; | |
| 110 | } | ||
| 111 | ✗ | return underlying(); | |
| 112 | } | ||
| 113 | ✗ | friend Derived operator + (Derived && a, Derived const& b) { return a += b; } | |
| 114 | ✗ | friend Derived operator + (Derived const& a, Derived && b) { | |
| 115 | ✗ | for (int64_t i = 1; i < layout.len; i++) { | |
| 116 | ✗ | b.st[i] = a.st[i] + b.st[i]; | |
| 117 | } | ||
| 118 | ✗ | return b; | |
| 119 | } | ||
| 120 | ✗ | friend Derived operator + (Derived && a, Derived && b) { return std::move(a) + b; } | |
| 121 | ✗ | friend Derived operator + (Derived const& a, Derived const& b) { return Derived(a) + b; } | |
| 122 | |||
| 123 | ✗ | template <typename F> Derived& operator += (F f) { | |
| 124 | ✗ | for (int64_t i = 1; i < layout.len; i++) { | |
| 125 | ✗ | underlying().st[i] += f(layout.get_bucket_bound(i)); | |
| 126 | } | ||
| 127 | ✗ | return underlying(); | |
| 128 | } | ||
| 129 | |||
| 130 | ✗ | Derived& operator -= (Derived const& o) { | |
| 131 | ✗ | for (int64_t i = 1; i < layout.len; i++) { | |
| 132 | ✗ | underlying().st[i] -= o.st[i]; | |
| 133 | } | ||
| 134 | ✗ | return underlying(); | |
| 135 | } | ||
| 136 | ✗ | friend Derived operator - (Derived && a, Derived const& b) { return a -= b; } | |
| 137 | ✗ | friend Derived operator - (Derived const& a, Derived && b) { | |
| 138 | ✗ | for (int64_t i = 1; i < layout.len; i++) { | |
| 139 | ✗ | b.st[i] = a.st[i] - b.st[i]; | |
| 140 | } | ||
| 141 | ✗ | return b; | |
| 142 | } | ||
| 143 | ✗ | friend Derived operator - (Derived && a, Derived && b) { return std::move(a) - b; } | |
| 144 | ✗ | friend Derived operator - (Derived const& a, Derived const& b) { return Derived(a) - b; } | |
| 145 | |||
| 146 | ✗ | template <typename F> Derived& operator -= (F f) { | |
| 147 | ✗ | for (int64_t i = 1; i < layout.len; i++) { | |
| 148 | ✗ | underlying().st[i] -= f(layout.get_bucket_bound(i)); | |
| 149 | } | ||
| 150 | ✗ | return underlying(); | |
| 151 | } | ||
| 152 | |||
| 153 | ✗ | Derived& operator *= (T const& t) { | |
| 154 | ✗ | for (int64_t i = 1; i < layout.len; i++) { | |
| 155 | ✗ | underlying().st[i] *= t; | |
| 156 | } | ||
| 157 | ✗ | return underlying(); | |
| 158 | } | ||
| 159 | ✗ | friend Derived operator * (Derived && a, T const& t) { return a *= t; } | |
| 160 | ✗ | friend Derived operator * (Derived const& a, T const& t) { return Derived(a) * t; } | |
| 161 | // Just in case, don't assume multiplication is commutative. | ||
| 162 | ✗ | friend Derived operator * (T const& t, Derived && a) { | |
| 163 | ✗ | for (int64_t i = 1; i < layout.len; i++) { | |
| 164 | ✗ | a.st[i] = t * a.st[i]; | |
| 165 | } | ||
| 166 | ✗ | return a; | |
| 167 | } | ||
| 168 | ✗ | friend Derived operator * (T const& t, Derived const& a) { return t * Derived(a); } | |
| 169 | |||
| 170 | ✗ | Derived& operator /= (T const& t) { | |
| 171 | ✗ | for (int64_t i = 1; i < layout.len; i++) { | |
| 172 | ✗ | underlying().st[i] /= t; | |
| 173 | } | ||
| 174 | ✗ | return underlying(); | |
| 175 | } | ||
| 176 | ✗ | friend Derived operator / (Derived && a, T const& t) { return a /= t; } | |
| 177 | ✗ | friend Derived operator / (Derived const& a, T const& t) { return Derived(a) / t; } | |
| 178 | }; | ||
| 179 | |||
| 180 | template <div_vector_layout const& layout, typename T> class values; | ||
| 181 | template <div_vector_layout const& layout, typename T> class prefix; | ||
| 182 | template <div_vector_layout const& layout, typename T> class bit; | ||
| 183 | |||
| 184 | 108 | template <div_vector_layout const& layout, typename T> class values : public div_vector<layout, T>, public vectorspace_mixin<layout, T, values<layout, T>> { | |
| 185 | public: | ||
| 186 |
3/3✓ Branch 5 → 67 taken 12 times.
✓ Branch 7 → 35 taken 12 times.
✓ Branch 80 → 101 taken 12 times.
|
96 | values() = default; |
| 187 | |||
| 188 | template <typename F, std::enable_if_t<std::is_invocable_r_v<T, F, int64_t, int64_t>, bool> = true> | ||
| 189 | ✗ | values(F f) { | |
| 190 | ✗ | for (int i = 1; i < layout.len; i++) { | |
| 191 | ✗ | this->st[i] = f(layout.get_bucket_bound(i-1), layout.get_bucket_bound(i)); | |
| 192 | } | ||
| 193 | } | ||
| 194 | |||
| 195 | ✗ | template <typename U> explicit values(values<layout, U> const& o) { | |
| 196 | ✗ | for (int i = 1; i < layout.len; i++) { | |
| 197 | ✗ | this->st[i] = T(o.st[i]); | |
| 198 | } | ||
| 199 | } | ||
| 200 | |||
| 201 | 12 | explicit values(prefix<layout, T> && o) : div_vector<layout, T>(static_cast<div_vector<layout, T>&&>(std::move(o))) { | |
| 202 |
2/2✓ Branch 22 → 11 taken 143 times.
✓ Branch 22 → 23 taken 12 times.
|
155 | for (int i = layout.len - 1; i > 1; i--) { |
| 203 | 143 | this->st[i] -= this->st[i-1]; | |
| 204 | } | ||
| 205 | 12 | } | |
| 206 | 120 | explicit values(prefix<layout, T> const& o) { | |
| 207 |
4/4dirichlet_series::values<dirichlet_series::test::layout, modnum<1000000007> >::values(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&):
✓ Branch 27 → 8 taken 310 times.
✓ Branch 27 → 28 taken 60 times.
dirichlet_series::values<dirichlet_series::test::layout, long>::values(dirichlet_series::prefix<dirichlet_series::test::layout, long> const&):
✓ Branch 24 → 8 taken 310 times.
✓ Branch 24 → 25 taken 60 times.
|
740 | for (int i = layout.len - 1; i > 1; i--) { |
| 208 | 620 | this->st[i] = o.st[i] - o.st[i-1]; | |
| 209 | } | ||
| 210 | 120 | this->st[1] = o.st[1]; | |
| 211 | 120 | } | |
| 212 | }; | ||
| 213 | |||
| 214 |
11/32✓ Branch 13 → 14 taken 48 times.
✗ Branch 13 → 15 not taken.
✓ Branch 15 → 16 taken 48 times.
✗ Branch 15 → 17 not taken.
✓ Branch 17 → 18 taken 30070 times.
✗ Branch 17 → 19 not taken.
✓ Branch 19 → 20 taken 30022 times.
✗ Branch 19 → 21 not taken.
✗ Branch 20 → 21 not taken.
✗ Branch 20 → 22 not taken.
✓ Branch 21 → 22 taken 60043 times.
✗ Branch 21 → 23 not taken.
✓ Branch 23 → 24 taken 30021 times.
✗ Branch 23 → 25 not taken.
✓ Branch 25 → 26 taken 30021 times.
✗ Branch 25 → 27 not taken.
✗ Branch 26 → 27 not taken.
✗ Branch 26 → 28 not taken.
✗ Branch 29 → 30 not taken.
✗ Branch 29 → 31 not taken.
✗ Branch 30 → 31 not taken.
✗ Branch 30 → 32 not taken.
✗ Branch 32 → 33 not taken.
✗ Branch 32 → 34 not taken.
✗ Branch 33 → 34 not taken.
✗ Branch 33 → 35 not taken.
✗ Branch 36 → 37 not taken.
✗ Branch 36 → 38 not taken.
✓ Branch 58 → 59 taken 12 times.
✓ Branch 71 → 72 taken 12 times.
✓ Branch 242 → 243 taken 12 times.
✓ Branch 255 → 256 taken 12 times.
|
247848 | template <div_vector_layout const& layout, typename T> class prefix : public div_vector<layout, T>, public vectorspace_mixin<layout, T, prefix<layout, T>> { |
| 215 | public: | ||
| 216 |
5/5✓ Branch 4 → 5 taken 1570 times.
✓ Branch 10 → 11 taken 30021 times.
✓ Branch 15 → 33 taken 12 times.
✓ Branch 101 → 115 taken 12 times.
✓ Branch 160 → 179 taken 12 times.
|
96128 | prefix() = default; |
| 217 | |||
| 218 | template <typename F, std::enable_if_t<std::is_invocable_r_v<T, F, int64_t>, bool> = true> | ||
| 219 | 33030 | prefix(F f) { | |
| 220 |
20/20dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> >::prefix<dirichlet_series::test::CATCH2_INTERNAL_TEMPLATE_TEST_0<modnum<1000000007> >()::{lambda(long)#2}, true>(dirichlet_series::test::CATCH2_INTERNAL_TEMPLATE_TEST_0<modnum<1000000007> >()::{lambda(long)#2}):
✓ Branch 20 → 6 taken 185 times.
✓ Branch 20 → 21 taken 30 times.
dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> >::prefix<dirichlet_series::test::CATCH2_INTERNAL_TEMPLATE_TEST_0<modnum<1000000007> >()::{lambda(long)#1}, true>(dirichlet_series::test::CATCH2_INTERNAL_TEMPLATE_TEST_0<modnum<1000000007> >()::{lambda(long)#1}):
✓ Branch 24 → 6 taken 185 times.
✓ Branch 24 → 25 taken 30 times.
dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> >::prefix<dirichlet_series::test::CATCH2_INTERNAL_TEMPLATE_TEST_9<modnum<1000000007> >()::{lambda(long)#2}, true>(dirichlet_series::test::CATCH2_INTERNAL_TEMPLATE_TEST_9<modnum<1000000007> >()::{lambda(long)#2}):
✓ Branch 20 → 6 taken 68290 times.
✓ Branch 20 → 21 taken 1390 times.
dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> >::prefix<dirichlet_series::test::CATCH2_INTERNAL_TEMPLATE_TEST_9<modnum<1000000007> >()::{lambda(long)#1}, true>(dirichlet_series::test::CATCH2_INTERNAL_TEMPLATE_TEST_9<modnum<1000000007> >()::{lambda(long)#1}):
✓ Branch 24 → 6 taken 68290 times.
✓ Branch 24 → 25 taken 1390 times.
dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> >::prefix<dirichlet_series::test::CATCH2_INTERNAL_TEMPLATE_TEST_16<modnum<1000000007> >()::{lambda(long)#1}, true>(dirichlet_series::test::CATCH2_INTERNAL_TEMPLATE_TEST_16<modnum<1000000007> >()::{lambda(long)#1}):
✓ Branch 20 → 6 taken 155 times.
✓ Branch 20 → 21 taken 12 times.
dirichlet_series::prefix<dirichlet_series::test::layout, long>::prefix<dirichlet_series::test::CATCH2_INTERNAL_TEMPLATE_TEST_0<long>()::{lambda(long)#2}, true>(dirichlet_series::test::CATCH2_INTERNAL_TEMPLATE_TEST_0<long>()::{lambda(long)#2}):
✓ Branch 15 → 6 taken 185 times.
✓ Branch 15 → 16 taken 30 times.
dirichlet_series::prefix<dirichlet_series::test::layout, long>::prefix<dirichlet_series::test::CATCH2_INTERNAL_TEMPLATE_TEST_0<long>()::{lambda(long)#1}, true>(dirichlet_series::test::CATCH2_INTERNAL_TEMPLATE_TEST_0<long>()::{lambda(long)#1}):
✓ Branch 15 → 6 taken 185 times.
✓ Branch 15 → 16 taken 30 times.
dirichlet_series::prefix<main::layout, modnum<998244353> >::prefix<main::{lambda(long)#2}, true>(main::{lambda(long)#2}):
✓ Branch 10 → 4 taken 6169160 times.
✓ Branch 10 → 11 taken 48 times.
dirichlet_series::prefix<main::layout, modnum<998244353> >::prefix<main::{lambda(long)#1}, true>(main::{lambda(long)#1}):
✓ Branch 5 → 4 taken 20424672 times.
✓ Branch 5 → 6 taken 30022 times.
✓ Branch 8 → 4 taken 6169160 times.
✓ Branch 8 → 9 taken 48 times.
|
32933497 | for (int i = 1; i < layout.len; i++) { |
| 221 |
1/2✗ Branch 6 → 7 not taken.
✓ Branch 6 → 8 taken 6169160 times.
|
39138102 | this->st[i] = f(layout.get_bucket_bound(i)); |
| 222 | } | ||
| 223 | 33030 | } | |
| 224 | |||
| 225 | ✗ | template <typename U> explicit prefix(prefix<layout, U> const& o) { | |
| 226 | ✗ | for (int i = 1; i < layout.len; i++) { | |
| 227 | ✗ | this->st[i] = T(o.st[i]); | |
| 228 | } | ||
| 229 | } | ||
| 230 | |||
| 231 | 84 | explicit prefix(values<layout, T> && o) : div_vector<layout, T>(static_cast<div_vector<layout, T>&&>(std::move(o))) { | |
| 232 |
4/4dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> >::prefix(dirichlet_series::values<dirichlet_series::test::layout, modnum<1000000007> >&&):
✓ Branch 22 → 9 taken 441 times.
✓ Branch 22 → 23 taken 54 times.
dirichlet_series::prefix<dirichlet_series::test::layout, long>::prefix(dirichlet_series::values<dirichlet_series::test::layout, long>&&):
✓ Branch 27 → 9 taken 155 times.
✓ Branch 27 → 28 taken 30 times.
|
680 | for (int i = 2; i < layout.len; i++) { |
| 233 | 596 | this->st[i] += this->st[i-1]; | |
| 234 | } | ||
| 235 | 84 | } | |
| 236 | 12 | explicit prefix(values<layout, T> const& o) { | |
| 237 | 12 | T pref = this->st[1] = o.st[1]; | |
| 238 |
2/2✓ Branch 43 → 27 taken 143 times.
✓ Branch 43 → 44 taken 12 times.
|
155 | for (int i = 2; i < layout.len; i++) { |
| 239 | 143 | this->st[i] = (pref += o.st[i]); | |
| 240 | } | ||
| 241 | 12 | } | |
| 242 | |||
| 243 | private: | ||
| 244 | // This essentially runs *this += a * b, except it doesn't convolve any | ||
| 245 | // terms involving 1*i and leaves those for the user-provided function f. | ||
| 246 | // (f is called for each i in [2, layout.len-1].) This allows us to | ||
| 247 | // easily implement multiplication or division or sqrt. (Note that a or b | ||
| 248 | // are allowed to be equal to this.) | ||
| 249 | template <typename F> | ||
| 250 | 63267 | void convolve_helper(prefix const& a, prefix const& b, F f) { | |
| 251 | // We roughly want to apply this[N/z] += a_val[x] * b_val[y] for all xyz <= N | ||
| 252 | // | ||
| 253 | // We'll split into the following cases (WLOG x <= y): | ||
| 254 | // 0a. x = 1 or y = 1 | ||
| 255 | // 0b. x = y > 1 | ||
| 256 | // 1. x < y <= z <= N/x/y | ||
| 257 | // 2. max(x, z) < y <= N/x/z | ||
| 258 | |||
| 259 | 63267 | T cur_sum = a.st[1] * b.st[1]; | |
| 260 |
14/14void dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> >::convolve_helper<dirichlet_series::sqrt(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&)::{lambda(int, modnum<1000000007>)#1}>(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::sqrt(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&)::{lambda(int, modnum<1000000007>)#1}):
✓ Branch 316 → 19 taken 310 times.
✓ Branch 316 → 317 taken 60 times.
void dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> >::convolve_helper<dirichlet_series::operator/(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&)::{lambda(int, modnum<1000000007>)#1}>(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::operator/(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&)::{lambda(int, modnum<1000000007>)#1}):
✓ Branch 316 → 19 taken 67210 times.
✓ Branch 316 → 317 taken 1450 times.
void dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> >::convolve_helper<dirichlet_series::operator*(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&)::{lambda(int, modnum<1000000007>)#1}>(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::operator*(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&)::{lambda(int, modnum<1000000007>)#1}):
✓ Branch 316 → 19 taken 68509 times.
✓ Branch 316 → 317 taken 1576 times.
void dirichlet_series::prefix<dirichlet_series::test::layout, long>::convolve_helper<dirichlet_series::operator/(dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::prefix<dirichlet_series::test::layout, long> const&)::{lambda(int, long)#1}>(dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::operator/(dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::prefix<dirichlet_series::test::layout, long> const&)::{lambda(int, long)#1}):
✓ Branch 253 → 13 taken 310 times.
✓ Branch 253 → 254 taken 60 times.
void dirichlet_series::prefix<dirichlet_series::test::layout, long>::convolve_helper<dirichlet_series::operator*(dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::prefix<dirichlet_series::test::layout, long> const&)::{lambda(int, long)#1}>(dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::operator*(dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::prefix<dirichlet_series::test::layout, long> const&)::{lambda(int, long)#1}):
✓ Branch 253 → 13 taken 155 times.
✓ Branch 253 → 254 taken 30 times.
void dirichlet_series::prefix<main::layout, modnum<998244353> >::convolve_helper<dirichlet_series::operator/(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&)::{lambda(int, modnum<998244353>)#1}>(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::operator/(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&)::{lambda(int, modnum<998244353>)#1}):
✓ Branch 76 → 3 taken 26563762 times.
✓ Branch 76 → 77 taken 30070 times.
void dirichlet_series::prefix<main::layout, modnum<998244353> >::convolve_helper<dirichlet_series::operator*(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&)::{lambda(int, modnum<998244353>)#1}>(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::operator*(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&)::{lambda(int, modnum<998244353>)#1}):
✓ Branch 76 → 3 taken 20394632 times.
✓ Branch 76 → 77 taken 30021 times.
|
47158155 | for (int i = 2; i < layout.len; i++) { |
| 261 | 47094888 | cur_sum += this->st[i]; | |
| 262 | |||
| 263 | // Case 2: max(x, z) < y <= N/x/z | ||
| 264 | // x^2 <= N / z | ||
| 265 | // x <= N / z / z | ||
| 266 |
14/14void dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> >::convolve_helper<dirichlet_series::sqrt(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&)::{lambda(int, modnum<1000000007>)#1}>(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::sqrt(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&)::{lambda(int, modnum<1000000007>)#1}):
✓ Branch 28 → 29 taken 198 times.
✓ Branch 28 → 141 taken 112 times.
void dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> >::convolve_helper<dirichlet_series::operator/(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&)::{lambda(int, modnum<1000000007>)#1}>(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::operator/(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&)::{lambda(int, modnum<1000000007>)#1}):
✓ Branch 28 → 29 taken 34473 times.
✓ Branch 28 → 141 taken 32737 times.
void dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> >::convolve_helper<dirichlet_series::operator*(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&)::{lambda(int, modnum<1000000007>)#1}>(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::operator*(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&)::{lambda(int, modnum<1000000007>)#1}):
✓ Branch 28 → 29 taken 35212 times.
✓ Branch 28 → 141 taken 33297 times.
void dirichlet_series::prefix<dirichlet_series::test::layout, long>::convolve_helper<dirichlet_series::operator/(dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::prefix<dirichlet_series::test::layout, long> const&)::{lambda(int, long)#1}>(dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::operator/(dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::prefix<dirichlet_series::test::layout, long> const&)::{lambda(int, long)#1}):
✓ Branch 22 → 23 taken 198 times.
✓ Branch 22 → 119 taken 112 times.
void dirichlet_series::prefix<dirichlet_series::test::layout, long>::convolve_helper<dirichlet_series::operator*(dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::prefix<dirichlet_series::test::layout, long> const&)::{lambda(int, long)#1}>(dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::operator*(dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::prefix<dirichlet_series::test::layout, long> const&)::{lambda(int, long)#1}):
✓ Branch 22 → 23 taken 99 times.
✓ Branch 22 → 119 taken 56 times.
void dirichlet_series::prefix<main::layout, modnum<998244353> >::convolve_helper<dirichlet_series::operator/(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&)::{lambda(int, modnum<998244353>)#1}>(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::operator/(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&)::{lambda(int, modnum<998244353>)#1}):
✓ Branch 4 → 5 taken 13304353 times.
✓ Branch 4 → 39 taken 13259409 times.
void dirichlet_series::prefix<main::layout, modnum<998244353> >::convolve_helper<dirichlet_series::operator*(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&)::{lambda(int, modnum<998244353>)#1}>(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::operator*(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&)::{lambda(int, modnum<998244353>)#1}):
✓ Branch 4 → 5 taken 10219755 times.
✓ Branch 4 → 39 taken 10174877 times.
|
47094888 | if (i >= layout.len - layout.rt) { |
| 267 | 23594288 | int z = int(layout.len - i); | |
| 268 | 23594288 | assert(z <= layout.rt); | |
| 269 |
5/10void dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> >::convolve_helper<dirichlet_series::sqrt(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&)::{lambda(int, modnum<1000000007>)#1}>(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::sqrt(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&)::{lambda(int, modnum<1000000007>)#1}):
✗ Branch 38 → 39 not taken.
✓ Branch 38 → 42 taken 198 times.
void dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> >::convolve_helper<dirichlet_series::operator/(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&)::{lambda(int, modnum<1000000007>)#1}>(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::operator/(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&)::{lambda(int, modnum<1000000007>)#1}):
✗ Branch 38 → 39 not taken.
✓ Branch 38 → 42 taken 34473 times.
void dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> >::convolve_helper<dirichlet_series::operator*(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&)::{lambda(int, modnum<1000000007>)#1}>(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::operator*(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&)::{lambda(int, modnum<1000000007>)#1}):
✗ Branch 38 → 39 not taken.
✓ Branch 38 → 42 taken 35212 times.
void dirichlet_series::prefix<dirichlet_series::test::layout, long>::convolve_helper<dirichlet_series::operator/(dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::prefix<dirichlet_series::test::layout, long> const&)::{lambda(int, long)#1}>(dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::operator/(dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::prefix<dirichlet_series::test::layout, long> const&)::{lambda(int, long)#1}):
✗ Branch 32 → 33 not taken.
✓ Branch 32 → 36 taken 198 times.
void dirichlet_series::prefix<dirichlet_series::test::layout, long>::convolve_helper<dirichlet_series::operator*(dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::prefix<dirichlet_series::test::layout, long> const&)::{lambda(int, long)#1}>(dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::operator*(dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::prefix<dirichlet_series::test::layout, long> const&)::{lambda(int, long)#1}):
✗ Branch 32 → 33 not taken.
✓ Branch 32 → 36 taken 99 times.
|
23594288 | int64_t rt_over_z = layout.rt/z; |
| 270 |
5/10void dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> >::convolve_helper<dirichlet_series::sqrt(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&)::{lambda(int, modnum<1000000007>)#1}>(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::sqrt(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&)::{lambda(int, modnum<1000000007>)#1}):
✗ Branch 45 → 46 not taken.
✓ Branch 45 → 48 taken 198 times.
void dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> >::convolve_helper<dirichlet_series::operator/(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&)::{lambda(int, modnum<1000000007>)#1}>(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::operator/(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&)::{lambda(int, modnum<1000000007>)#1}):
✗ Branch 45 → 46 not taken.
✓ Branch 45 → 48 taken 34473 times.
void dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> >::convolve_helper<dirichlet_series::operator*(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&)::{lambda(int, modnum<1000000007>)#1}>(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::operator*(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&)::{lambda(int, modnum<1000000007>)#1}):
✗ Branch 45 → 46 not taken.
✓ Branch 45 → 48 taken 35212 times.
void dirichlet_series::prefix<dirichlet_series::test::layout, long>::convolve_helper<dirichlet_series::operator/(dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::prefix<dirichlet_series::test::layout, long> const&)::{lambda(int, long)#1}>(dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::operator/(dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::prefix<dirichlet_series::test::layout, long> const&)::{lambda(int, long)#1}):
✗ Branch 39 → 40 not taken.
✓ Branch 39 → 42 taken 198 times.
void dirichlet_series::prefix<dirichlet_series::test::layout, long>::convolve_helper<dirichlet_series::operator*(dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::prefix<dirichlet_series::test::layout, long> const&)::{lambda(int, long)#1}>(dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::operator*(dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::prefix<dirichlet_series::test::layout, long> const&)::{lambda(int, long)#1}):
✗ Branch 39 → 40 not taken.
✓ Branch 39 → 42 taken 99 times.
|
23594288 | int64_t N_over_z = layout.N/z; |
| 271 |
5/10void dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> >::convolve_helper<dirichlet_series::sqrt(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&)::{lambda(int, modnum<1000000007>)#1}>(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::sqrt(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&)::{lambda(int, modnum<1000000007>)#1}):
✗ Branch 49 → 50 not taken.
✓ Branch 49 → 51 taken 198 times.
void dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> >::convolve_helper<dirichlet_series::operator/(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&)::{lambda(int, modnum<1000000007>)#1}>(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::operator/(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&)::{lambda(int, modnum<1000000007>)#1}):
✗ Branch 49 → 50 not taken.
✓ Branch 49 → 51 taken 34473 times.
void dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> >::convolve_helper<dirichlet_series::operator*(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&)::{lambda(int, modnum<1000000007>)#1}>(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::operator*(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&)::{lambda(int, modnum<1000000007>)#1}):
✗ Branch 49 → 50 not taken.
✓ Branch 49 → 51 taken 35212 times.
void dirichlet_series::prefix<dirichlet_series::test::layout, long>::convolve_helper<dirichlet_series::operator/(dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::prefix<dirichlet_series::test::layout, long> const&)::{lambda(int, long)#1}>(dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::operator/(dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::prefix<dirichlet_series::test::layout, long> const&)::{lambda(int, long)#1}):
✗ Branch 43 → 44 not taken.
✓ Branch 43 → 45 taken 198 times.
void dirichlet_series::prefix<dirichlet_series::test::layout, long>::convolve_helper<dirichlet_series::operator*(dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::prefix<dirichlet_series::test::layout, long> const&)::{lambda(int, long)#1}>(dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::operator*(dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::prefix<dirichlet_series::test::layout, long> const&)::{lambda(int, long)#1}):
✗ Branch 43 → 44 not taken.
✓ Branch 43 → 45 taken 99 times.
|
23594288 | int64_t x_max = N_over_z/(z+1); |
| 272 | |||
| 273 | 23594288 | T tot_val = T(); | |
| 274 |
28/28void dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> >::convolve_helper<dirichlet_series::sqrt(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&)::{lambda(int, modnum<1000000007>)#1}>(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::sqrt(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&)::{lambda(int, modnum<1000000007>)#1}):
✓ Branch 127 → 128 taken 206 times.
✓ Branch 127 → 129 taken 170 times.
✓ Branch 128 → 56 taken 178 times.
✓ Branch 128 → 129 taken 28 times.
void dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> >::convolve_helper<dirichlet_series::operator/(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&)::{lambda(int, modnum<1000000007>)#1}>(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::operator/(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&)::{lambda(int, modnum<1000000007>)#1}):
✓ Branch 127 → 128 taken 198233 times.
✓ Branch 127 → 129 taken 11768 times.
✓ Branch 128 → 56 taken 175528 times.
✓ Branch 128 → 129 taken 22705 times.
void dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> >::convolve_helper<dirichlet_series::operator*(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&)::{lambda(int, modnum<1000000007>)#1}>(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::operator*(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&)::{lambda(int, modnum<1000000007>)#1}):
✓ Branch 127 → 128 taken 200696 times.
✓ Branch 127 → 129 taken 12173 times.
✓ Branch 128 → 56 taken 177657 times.
✓ Branch 128 → 129 taken 23039 times.
void dirichlet_series::prefix<dirichlet_series::test::layout, long>::convolve_helper<dirichlet_series::operator/(dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::prefix<dirichlet_series::test::layout, long> const&)::{lambda(int, long)#1}>(dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::operator/(dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::prefix<dirichlet_series::test::layout, long> const&)::{lambda(int, long)#1}):
✓ Branch 102 → 103 taken 206 times.
✓ Branch 102 → 104 taken 170 times.
✓ Branch 103 → 46 taken 178 times.
✓ Branch 103 → 104 taken 28 times.
void dirichlet_series::prefix<dirichlet_series::test::layout, long>::convolve_helper<dirichlet_series::operator*(dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::prefix<dirichlet_series::test::layout, long> const&)::{lambda(int, long)#1}>(dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::operator*(dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::prefix<dirichlet_series::test::layout, long> const&)::{lambda(int, long)#1}):
✓ Branch 102 → 103 taken 103 times.
✓ Branch 102 → 104 taken 85 times.
✓ Branch 103 → 46 taken 89 times.
✓ Branch 103 → 104 taken 14 times.
void dirichlet_series::prefix<main::layout, modnum<998244353> >::convolve_helper<dirichlet_series::operator/(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&)::{lambda(int, modnum<998244353>)#1}>(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::operator/(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&)::{lambda(int, modnum<998244353>)#1}):
✓ Branch 30 → 31 taken 2753075263 times.
✓ Branch 30 → 32 taken 631299 times.
✓ Branch 31 → 8 taken 2740402209 times.
✓ Branch 31 → 32 taken 12673054 times.
void dirichlet_series::prefix<main::layout, modnum<998244353> >::convolve_helper<dirichlet_series::operator*(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&)::{lambda(int, modnum<998244353>)#1}>(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::operator*(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&)::{lambda(int, modnum<998244353>)#1}):
✓ Branch 30 → 31 taken 2361439087 times.
✓ Branch 30 → 32 taken 559496 times.
✓ Branch 31 → 8 taken 2351778828 times.
✓ Branch 31 → 32 taken 9660259 times.
|
5116128955 | for (int64_t x = 2; x * (x+1) <= N_over_z && x <= x_max; x++) { |
| 275 | // ylo = std::max(x, z) | ||
| 276 |
4/4void dirichlet_series::prefix<main::layout, modnum<998244353> >::convolve_helper<dirichlet_series::operator/(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&)::{lambda(int, modnum<998244353>)#1}>(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::operator/(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&)::{lambda(int, modnum<998244353>)#1}):
✓ Branch 8 → 9 taken 144690527 times.
✓ Branch 8 → 10 taken 2595711682 times.
void dirichlet_series::prefix<main::layout, modnum<998244353> >::convolve_helper<dirichlet_series::operator*(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&)::{lambda(int, modnum<998244353>)#1}>(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::operator*(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&)::{lambda(int, modnum<998244353>)#1}):
✓ Branch 8 → 9 taken 112463007 times.
✓ Branch 8 → 10 taken 2239315821 times.
|
5092534667 | int ylo_idx = std::max(int(x), z); |
| 277 | // yhi = N / x / z | ||
| 278 |
19/24void dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> >::convolve_helper<dirichlet_series::sqrt(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&)::{lambda(int, modnum<1000000007>)#1}>(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::sqrt(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&)::{lambda(int, modnum<1000000007>)#1}):
✓ Branch 62 → 63 taken 142 times.
✓ Branch 62 → 66 taken 36 times.
✗ Branch 66 → 67 not taken.
✓ Branch 66 → 68 taken 36 times.
void dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> >::convolve_helper<dirichlet_series::operator/(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&)::{lambda(int, modnum<1000000007>)#1}>(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::operator/(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&)::{lambda(int, modnum<1000000007>)#1}):
✓ Branch 62 → 63 taken 87044 times.
✓ Branch 62 → 66 taken 88484 times.
✗ Branch 66 → 67 not taken.
✓ Branch 66 → 68 taken 88484 times.
void dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> >::convolve_helper<dirichlet_series::operator*(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&)::{lambda(int, modnum<1000000007>)#1}>(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::operator*(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&)::{lambda(int, modnum<1000000007>)#1}):
✓ Branch 62 → 63 taken 88235 times.
✓ Branch 62 → 66 taken 89422 times.
✗ Branch 66 → 67 not taken.
✓ Branch 66 → 68 taken 89422 times.
void dirichlet_series::prefix<dirichlet_series::test::layout, long>::convolve_helper<dirichlet_series::operator/(dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::prefix<dirichlet_series::test::layout, long> const&)::{lambda(int, long)#1}>(dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::operator/(dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::prefix<dirichlet_series::test::layout, long> const&)::{lambda(int, long)#1}):
✓ Branch 52 → 53 taken 142 times.
✓ Branch 52 → 56 taken 36 times.
✗ Branch 56 → 57 not taken.
✓ Branch 56 → 58 taken 36 times.
void dirichlet_series::prefix<dirichlet_series::test::layout, long>::convolve_helper<dirichlet_series::operator*(dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::prefix<dirichlet_series::test::layout, long> const&)::{lambda(int, long)#1}>(dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::operator*(dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::prefix<dirichlet_series::test::layout, long> const&)::{lambda(int, long)#1}):
✓ Branch 52 → 53 taken 71 times.
✓ Branch 52 → 56 taken 18 times.
✗ Branch 56 → 57 not taken.
✓ Branch 56 → 58 taken 18 times.
void dirichlet_series::prefix<main::layout, modnum<998244353> >::convolve_helper<dirichlet_series::operator/(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&)::{lambda(int, modnum<998244353>)#1}>(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::operator/(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&)::{lambda(int, modnum<998244353>)#1}):
✓ Branch 8 → 9 taken 144690527 times.
✓ Branch 8 → 10 taken 2595711682 times.
void dirichlet_series::prefix<main::layout, modnum<998244353> >::convolve_helper<dirichlet_series::operator*(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&)::{lambda(int, modnum<998244353>)#1}>(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::operator*(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&)::{lambda(int, modnum<998244353>)#1}):
✓ Branch 8 → 9 taken 112463007 times.
✓ Branch 8 → 10 taken 2239315821 times.
|
5092534667 | int yhi_idx = int(x <= rt_over_z ? layout.len - x * z : N_over_z / x); |
| 279 | 5092534667 | assert(ylo_idx < yhi_idx); | |
| 280 | |||
| 281 |
4/4void dirichlet_series::prefix<main::layout, modnum<998244353> >::convolve_helper<dirichlet_series::operator/(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&)::{lambda(int, modnum<998244353>)#1}>(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::operator/(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&)::{lambda(int, modnum<998244353>)#1}):
✓ Branch 13 → 14 taken 1182650394 times.
✓ Branch 13 → 15 taken 1557751815 times.
void dirichlet_series::prefix<main::layout, modnum<998244353> >::convolve_helper<dirichlet_series::operator*(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&)::{lambda(int, modnum<998244353>)#1}>(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::operator*(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&)::{lambda(int, modnum<998244353>)#1}):
✓ Branch 13 → 14 taken 1181448144 times.
✓ Branch 13 → 15 taken 1170330684 times.
|
5092534667 | T ax = a.st[x] - a.st[x-1]; |
| 282 |
4/4void dirichlet_series::prefix<main::layout, modnum<998244353> >::convolve_helper<dirichlet_series::operator/(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&)::{lambda(int, modnum<998244353>)#1}>(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::operator/(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&)::{lambda(int, modnum<998244353>)#1}):
✓ Branch 16 → 17 taken 1182555317 times.
✓ Branch 16 → 18 taken 1557846892 times.
void dirichlet_series::prefix<main::layout, modnum<998244353> >::convolve_helper<dirichlet_series::operator*(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&)::{lambda(int, modnum<998244353>)#1}>(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::operator*(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&)::{lambda(int, modnum<998244353>)#1}):
✓ Branch 16 → 17 taken 1178777760 times.
✓ Branch 16 → 18 taken 1173001068 times.
|
5092534667 | T bx = b.st[x] - b.st[x-1]; |
| 283 |
4/4void dirichlet_series::prefix<main::layout, modnum<998244353> >::convolve_helper<dirichlet_series::operator/(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&)::{lambda(int, modnum<998244353>)#1}>(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::operator/(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&)::{lambda(int, modnum<998244353>)#1}):
✓ Branch 19 → 20 taken 1181027635 times.
✓ Branch 19 → 21 taken 1559374574 times.
void dirichlet_series::prefix<main::layout, modnum<998244353> >::convolve_helper<dirichlet_series::operator*(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&)::{lambda(int, modnum<998244353>)#1}>(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::operator*(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&)::{lambda(int, modnum<998244353>)#1}):
✓ Branch 19 → 20 taken 1177228792 times.
✓ Branch 19 → 21 taken 1174550036 times.
|
5092534667 | T ay = a.st[yhi_idx] - a.st[ylo_idx]; |
| 284 |
8/8void dirichlet_series::prefix<main::layout, modnum<998244353> >::convolve_helper<dirichlet_series::operator/(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&)::{lambda(int, modnum<998244353>)#1}>(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::operator/(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&)::{lambda(int, modnum<998244353>)#1}):
✓ Branch 22 → 23 taken 1177343913 times.
✓ Branch 22 → 24 taken 1563058296 times.
✓ Branch 25 → 26 taken 1555896728 times.
✓ Branch 25 → 27 taken 1184505481 times.
void dirichlet_series::prefix<main::layout, modnum<998244353> >::convolve_helper<dirichlet_series::operator*(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&)::{lambda(int, modnum<998244353>)#1}>(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::operator*(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&)::{lambda(int, modnum<998244353>)#1}):
✓ Branch 22 → 23 taken 1178549647 times.
✓ Branch 22 → 24 taken 1173229181 times.
✓ Branch 25 → 26 taken 1175930577 times.
✓ Branch 25 → 27 taken 1175848251 times.
|
777600346 | T by = b.st[yhi_idx] - b.st[ylo_idx]; |
| 285 | |||
| 286 |
4/4void dirichlet_series::prefix<main::layout, modnum<998244353> >::convolve_helper<dirichlet_series::operator/(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&)::{lambda(int, modnum<998244353>)#1}>(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::operator/(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&)::{lambda(int, modnum<998244353>)#1}):
✓ Branch 25 → 26 taken 1555896728 times.
✓ Branch 25 → 27 taken 1184505481 times.
void dirichlet_series::prefix<main::layout, modnum<998244353> >::convolve_helper<dirichlet_series::operator*(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&)::{lambda(int, modnum<998244353>)#1}>(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::operator*(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&)::{lambda(int, modnum<998244353>)#1}):
✓ Branch 25 → 26 taken 1175930577 times.
✓ Branch 25 → 27 taken 1175848251 times.
|
5092534667 | T v = ax * by + ay * bx; |
| 287 | 5092534667 | tot_val += v; | |
| 288 | } | ||
| 289 | 23594288 | cur_sum += tot_val; | |
| 290 |
14/14void dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> >::convolve_helper<dirichlet_series::sqrt(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&)::{lambda(int, modnum<1000000007>)#1}>(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::sqrt(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&)::{lambda(int, modnum<1000000007>)#1}):
✓ Branch 132 → 133 taken 140 times.
✓ Branch 132 → 139 taken 58 times.
void dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> >::convolve_helper<dirichlet_series::operator/(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&)::{lambda(int, modnum<1000000007>)#1}>(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::operator/(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&)::{lambda(int, modnum<1000000007>)#1}):
✓ Branch 132 → 133 taken 33026 times.
✓ Branch 132 → 139 taken 1447 times.
void dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> >::convolve_helper<dirichlet_series::operator*(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&)::{lambda(int, modnum<1000000007>)#1}>(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::operator*(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&)::{lambda(int, modnum<1000000007>)#1}):
✓ Branch 132 → 133 taken 33648 times.
✓ Branch 132 → 139 taken 1564 times.
void dirichlet_series::prefix<dirichlet_series::test::layout, long>::convolve_helper<dirichlet_series::operator/(dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::prefix<dirichlet_series::test::layout, long> const&)::{lambda(int, long)#1}>(dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::operator/(dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::prefix<dirichlet_series::test::layout, long> const&)::{lambda(int, long)#1}):
✓ Branch 106 → 107 taken 140 times.
✓ Branch 106 → 118 taken 58 times.
void dirichlet_series::prefix<dirichlet_series::test::layout, long>::convolve_helper<dirichlet_series::operator*(dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::prefix<dirichlet_series::test::layout, long> const&)::{lambda(int, long)#1}>(dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::operator*(dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::prefix<dirichlet_series::test::layout, long> const&)::{lambda(int, long)#1}):
✓ Branch 106 → 107 taken 70 times.
✓ Branch 106 → 118 taken 29 times.
void dirichlet_series::prefix<main::layout, modnum<998244353> >::convolve_helper<dirichlet_series::operator/(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&)::{lambda(int, modnum<998244353>)#1}>(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::operator/(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&)::{lambda(int, modnum<998244353>)#1}):
✓ Branch 33 → 34 taken 13274288 times.
✓ Branch 33 → 38 taken 30065 times.
void dirichlet_series::prefix<main::layout, modnum<998244353> >::convolve_helper<dirichlet_series::operator*(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&)::{lambda(int, modnum<998244353>)#1}>(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::operator*(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&)::{lambda(int, modnum<998244353>)#1}):
✓ Branch 33 → 34 taken 10189738 times.
✓ Branch 33 → 38 taken 30017 times.
|
23594288 | if (i+1 < layout.len) { |
| 291 |
4/4void dirichlet_series::prefix<main::layout, modnum<998244353> >::convolve_helper<dirichlet_series::operator/(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&)::{lambda(int, modnum<998244353>)#1}>(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::operator/(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&)::{lambda(int, modnum<998244353>)#1}):
✓ Branch 34 → 35 taken 5080980 times.
✓ Branch 34 → 36 taken 8193308 times.
void dirichlet_series::prefix<main::layout, modnum<998244353> >::convolve_helper<dirichlet_series::operator*(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&)::{lambda(int, modnum<998244353>)#1}>(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::operator*(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&)::{lambda(int, modnum<998244353>)#1}):
✓ Branch 34 → 35 taken 3590505 times.
✓ Branch 34 → 36 taken 6599233 times.
|
46995076 | this->st[i+1] -= tot_val; |
| 292 | } | ||
| 293 | } | ||
| 294 | |||
| 295 | 47094888 | this->st[i] = f(i, cur_sum); | |
| 296 | |||
| 297 |
4/4void dirichlet_series::prefix<main::layout, modnum<998244353> >::convolve_helper<dirichlet_series::operator/(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&)::{lambda(int, modnum<998244353>)#1}>(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::operator/(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&)::{lambda(int, modnum<998244353>)#1}):
✓ Branch 39 → 40 taken 10308309 times.
✓ Branch 39 → 41 taken 16255453 times.
void dirichlet_series::prefix<main::layout, modnum<998244353> >::convolve_helper<dirichlet_series::operator*(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&)::{lambda(int, modnum<998244353>)#1}>(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::operator*(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&)::{lambda(int, modnum<998244353>)#1}):
✓ Branch 39 → 40 taken 10199624 times.
✓ Branch 39 → 41 taken 10195008 times.
|
47094888 | T ai = a.st[i] - a.st[i-1]; |
| 298 |
4/4void dirichlet_series::prefix<main::layout, modnum<998244353> >::convolve_helper<dirichlet_series::operator/(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&)::{lambda(int, modnum<998244353>)#1}>(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::operator/(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&)::{lambda(int, modnum<998244353>)#1}):
✓ Branch 42 → 43 taken 10200501 times.
✓ Branch 42 → 44 taken 16363261 times.
void dirichlet_series::prefix<main::layout, modnum<998244353> >::convolve_helper<dirichlet_series::operator*(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&)::{lambda(int, modnum<998244353>)#1}>(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::operator*(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&)::{lambda(int, modnum<998244353>)#1}):
✓ Branch 42 → 43 taken 10196213 times.
✓ Branch 42 → 44 taken 10198419 times.
|
47094888 | T bi = b.st[i] - b.st[i-1]; |
| 299 | |||
| 300 | // Case 0a: x = 1 | ||
| 301 |
4/4void dirichlet_series::prefix<main::layout, modnum<998244353> >::convolve_helper<dirichlet_series::operator/(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&)::{lambda(int, modnum<998244353>)#1}>(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::operator/(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&)::{lambda(int, modnum<998244353>)#1}):
✓ Branch 45 → 46 taken 15671124 times.
✓ Branch 45 → 47 taken 10892638 times.
void dirichlet_series::prefix<main::layout, modnum<998244353> >::convolve_helper<dirichlet_series::operator*(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&)::{lambda(int, modnum<998244353>)#1}>(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::operator*(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&)::{lambda(int, modnum<998244353>)#1}):
✓ Branch 45 → 46 taken 10197067 times.
✓ Branch 45 → 47 taken 10197565 times.
|
94053282 | cur_sum += ai * b.st[1] + a.st[1] * bi; |
| 302 | |||
| 303 |
14/14void dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> >::convolve_helper<dirichlet_series::sqrt(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&)::{lambda(int, modnum<1000000007>)#1}>(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::sqrt(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&)::{lambda(int, modnum<1000000007>)#1}):
✓ Branch 200 → 201 taken 140 times.
✓ Branch 200 → 311 taken 170 times.
void dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> >::convolve_helper<dirichlet_series::operator/(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&)::{lambda(int, modnum<1000000007>)#1}>(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::operator/(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&)::{lambda(int, modnum<1000000007>)#1}):
✓ Branch 200 → 201 taken 33026 times.
✓ Branch 200 → 311 taken 34184 times.
void dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> >::convolve_helper<dirichlet_series::operator*(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&)::{lambda(int, modnum<1000000007>)#1}>(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::operator*(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&)::{lambda(int, modnum<1000000007>)#1}):
✓ Branch 200 → 201 taken 33648 times.
✓ Branch 200 → 311 taken 34861 times.
void dirichlet_series::prefix<dirichlet_series::test::layout, long>::convolve_helper<dirichlet_series::operator/(dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::prefix<dirichlet_series::test::layout, long> const&)::{lambda(int, long)#1}>(dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::operator/(dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::prefix<dirichlet_series::test::layout, long> const&)::{lambda(int, long)#1}):
✓ Branch 157 → 158 taken 140 times.
✓ Branch 157 → 250 taken 170 times.
void dirichlet_series::prefix<dirichlet_series::test::layout, long>::convolve_helper<dirichlet_series::operator*(dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::prefix<dirichlet_series::test::layout, long> const&)::{lambda(int, long)#1}>(dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::operator*(dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::prefix<dirichlet_series::test::layout, long> const&)::{lambda(int, long)#1}):
✓ Branch 157 → 158 taken 70 times.
✓ Branch 157 → 250 taken 85 times.
void dirichlet_series::prefix<main::layout, modnum<998244353> >::convolve_helper<dirichlet_series::operator/(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&)::{lambda(int, modnum<998244353>)#1}>(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::operator/(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&)::{lambda(int, modnum<998244353>)#1}):
✓ Branch 49 → 50 taken 13274288 times.
✓ Branch 49 → 75 taken 13289474 times.
void dirichlet_series::prefix<main::layout, modnum<998244353> >::convolve_helper<dirichlet_series::operator*(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&)::{lambda(int, modnum<998244353>)#1}>(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::operator*(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&)::{lambda(int, modnum<998244353>)#1}):
✓ Branch 49 → 50 taken 10189738 times.
✓ Branch 49 → 75 taken 10204894 times.
|
47094888 | if (i <= layout.rt) { |
| 304 | // Case 1: x < y <= z <= N/x/y (y = i) | ||
| 305 | // xy <= z <= N/y | ||
| 306 |
5/10void dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> >::convolve_helper<dirichlet_series::sqrt(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&)::{lambda(int, modnum<1000000007>)#1}>(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::sqrt(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&)::{lambda(int, modnum<1000000007>)#1}):
✗ Branch 203 → 204 not taken.
✓ Branch 203 → 207 taken 140 times.
void dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> >::convolve_helper<dirichlet_series::operator/(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&)::{lambda(int, modnum<1000000007>)#1}>(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::operator/(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&)::{lambda(int, modnum<1000000007>)#1}):
✗ Branch 203 → 204 not taken.
✓ Branch 203 → 207 taken 33026 times.
void dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> >::convolve_helper<dirichlet_series::operator*(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&)::{lambda(int, modnum<1000000007>)#1}>(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::operator*(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&)::{lambda(int, modnum<1000000007>)#1}):
✗ Branch 203 → 204 not taken.
✓ Branch 203 → 207 taken 33648 times.
void dirichlet_series::prefix<dirichlet_series::test::layout, long>::convolve_helper<dirichlet_series::operator/(dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::prefix<dirichlet_series::test::layout, long> const&)::{lambda(int, long)#1}>(dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::operator/(dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::prefix<dirichlet_series::test::layout, long> const&)::{lambda(int, long)#1}):
✗ Branch 160 → 161 not taken.
✓ Branch 160 → 164 taken 140 times.
void dirichlet_series::prefix<dirichlet_series::test::layout, long>::convolve_helper<dirichlet_series::operator*(dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::prefix<dirichlet_series::test::layout, long> const&)::{lambda(int, long)#1}>(dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::operator*(dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::prefix<dirichlet_series::test::layout, long> const&)::{lambda(int, long)#1}):
✗ Branch 160 → 161 not taken.
✓ Branch 160 → 164 taken 70 times.
|
23531050 | int64_t rt_over_i = layout.rt / i; |
| 307 |
5/10void dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> >::convolve_helper<dirichlet_series::sqrt(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&)::{lambda(int, modnum<1000000007>)#1}>(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::sqrt(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&)::{lambda(int, modnum<1000000007>)#1}):
✗ Branch 210 → 211 not taken.
✓ Branch 210 → 213 taken 140 times.
void dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> >::convolve_helper<dirichlet_series::operator/(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&)::{lambda(int, modnum<1000000007>)#1}>(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::operator/(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&)::{lambda(int, modnum<1000000007>)#1}):
✗ Branch 210 → 211 not taken.
✓ Branch 210 → 213 taken 33026 times.
void dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> >::convolve_helper<dirichlet_series::operator*(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&)::{lambda(int, modnum<1000000007>)#1}>(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::operator*(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&)::{lambda(int, modnum<1000000007>)#1}):
✗ Branch 210 → 211 not taken.
✓ Branch 210 → 213 taken 33648 times.
void dirichlet_series::prefix<dirichlet_series::test::layout, long>::convolve_helper<dirichlet_series::operator/(dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::prefix<dirichlet_series::test::layout, long> const&)::{lambda(int, long)#1}>(dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::operator/(dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::prefix<dirichlet_series::test::layout, long> const&)::{lambda(int, long)#1}):
✗ Branch 167 → 168 not taken.
✓ Branch 167 → 170 taken 140 times.
void dirichlet_series::prefix<dirichlet_series::test::layout, long>::convolve_helper<dirichlet_series::operator*(dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::prefix<dirichlet_series::test::layout, long> const&)::{lambda(int, long)#1}>(dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::operator*(dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::prefix<dirichlet_series::test::layout, long> const&)::{lambda(int, long)#1}):
✗ Branch 167 → 168 not taken.
✓ Branch 167 → 170 taken 70 times.
|
23531050 | int64_t N_over_i = layout.N / i; |
| 308 |
5/10void dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> >::convolve_helper<dirichlet_series::sqrt(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&)::{lambda(int, modnum<1000000007>)#1}>(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::sqrt(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&)::{lambda(int, modnum<1000000007>)#1}):
✗ Branch 217 → 218 not taken.
✓ Branch 217 → 219 taken 140 times.
void dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> >::convolve_helper<dirichlet_series::operator/(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&)::{lambda(int, modnum<1000000007>)#1}>(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::operator/(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&)::{lambda(int, modnum<1000000007>)#1}):
✗ Branch 217 → 218 not taken.
✓ Branch 217 → 219 taken 33026 times.
void dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> >::convolve_helper<dirichlet_series::operator*(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&)::{lambda(int, modnum<1000000007>)#1}>(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::operator*(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&)::{lambda(int, modnum<1000000007>)#1}):
✗ Branch 217 → 218 not taken.
✓ Branch 217 → 219 taken 33648 times.
void dirichlet_series::prefix<dirichlet_series::test::layout, long>::convolve_helper<dirichlet_series::operator/(dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::prefix<dirichlet_series::test::layout, long> const&)::{lambda(int, long)#1}>(dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::operator/(dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::prefix<dirichlet_series::test::layout, long> const&)::{lambda(int, long)#1}):
✗ Branch 174 → 175 not taken.
✓ Branch 174 → 176 taken 140 times.
void dirichlet_series::prefix<dirichlet_series::test::layout, long>::convolve_helper<dirichlet_series::operator*(dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::prefix<dirichlet_series::test::layout, long> const&)::{lambda(int, long)#1}>(dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::operator*(dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::prefix<dirichlet_series::test::layout, long> const&)::{lambda(int, long)#1}):
✗ Branch 174 → 175 not taken.
✓ Branch 174 → 176 taken 70 times.
|
23531050 | int x_max = int(std::min<int64_t>(N_over_i / i, i-1)); |
| 309 | 23531050 | T tot_sub = T(); | |
| 310 |
14/14void dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> >::convolve_helper<dirichlet_series::sqrt(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&)::{lambda(int, modnum<1000000007>)#1}>(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::sqrt(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&)::{lambda(int, modnum<1000000007>)#1}):
✓ Branch 287 → 230 taken 26 times.
✓ Branch 287 → 288 taken 140 times.
void dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> >::convolve_helper<dirichlet_series::operator/(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&)::{lambda(int, modnum<1000000007>)#1}>(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::operator/(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&)::{lambda(int, modnum<1000000007>)#1}):
✓ Branch 287 → 230 taken 71402 times.
✓ Branch 287 → 288 taken 33026 times.
void dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> >::convolve_helper<dirichlet_series::operator*(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&)::{lambda(int, modnum<1000000007>)#1}>(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::operator*(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&)::{lambda(int, modnum<1000000007>)#1}):
✓ Branch 287 → 230 taken 72175 times.
✓ Branch 287 → 288 taken 33648 times.
void dirichlet_series::prefix<dirichlet_series::test::layout, long>::convolve_helper<dirichlet_series::operator/(dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::prefix<dirichlet_series::test::layout, long> const&)::{lambda(int, long)#1}>(dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::operator/(dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::prefix<dirichlet_series::test::layout, long> const&)::{lambda(int, long)#1}):
✓ Branch 221 → 183 taken 26 times.
✓ Branch 221 → 222 taken 140 times.
void dirichlet_series::prefix<dirichlet_series::test::layout, long>::convolve_helper<dirichlet_series::operator*(dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::prefix<dirichlet_series::test::layout, long> const&)::{lambda(int, long)#1}>(dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::operator*(dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::prefix<dirichlet_series::test::layout, long> const&)::{lambda(int, long)#1}):
✓ Branch 221 → 183 taken 13 times.
✓ Branch 221 → 222 taken 70 times.
void dirichlet_series::prefix<main::layout, modnum<998244353> >::convolve_helper<dirichlet_series::operator/(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&)::{lambda(int, modnum<998244353>)#1}>(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::operator/(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&)::{lambda(int, modnum<998244353>)#1}):
✓ Branch 66 → 51 taken 1363565760 times.
✓ Branch 66 → 67 taken 13274288 times.
void dirichlet_series::prefix<main::layout, modnum<998244353> >::convolve_helper<dirichlet_series::operator*(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&)::{lambda(int, modnum<998244353>)#1}>(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::operator*(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&)::{lambda(int, modnum<998244353>)#1}):
✓ Branch 66 → 51 taken 1170796948 times.
✓ Branch 66 → 67 taken 10189738 times.
|
2558037400 | for (int x = 2; x <= x_max; x++) { |
| 311 | 2534506311 | T v; | |
| 312 |
12/12void dirichlet_series::prefix<main::layout, modnum<998244353> >::convolve_helper<dirichlet_series::operator/(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&)::{lambda(int, modnum<998244353>)#1}>(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::operator/(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&)::{lambda(int, modnum<998244353>)#1}):
✓ Branch 51 → 52 taken 590898758 times.
✓ Branch 51 → 53 taken 772667002 times.
✓ Branch 54 → 55 taken 591709094 times.
✓ Branch 54 → 56 taken 771856666 times.
✓ Branch 57 → 58 taken 778187961 times.
✓ Branch 57 → 59 taken 585377799 times.
void dirichlet_series::prefix<main::layout, modnum<998244353> >::convolve_helper<dirichlet_series::operator*(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&)::{lambda(int, modnum<998244353>)#1}>(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::operator*(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&)::{lambda(int, modnum<998244353>)#1}):
✓ Branch 51 → 52 taken 590603920 times.
✓ Branch 51 → 53 taken 580193028 times.
✓ Branch 54 → 55 taken 589089893 times.
✓ Branch 54 → 56 taken 581707055 times.
✓ Branch 57 → 58 taken 585392735 times.
✓ Branch 57 → 59 taken 585404213 times.
|
7603231766 | v = ai * (b.st[x] - b.st[x-1]) + (a.st[x] - a.st[x-1]) * bi; |
| 313 | |||
| 314 |
16/24void dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> >::convolve_helper<dirichlet_series::sqrt(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&)::{lambda(int, modnum<1000000007>)#1}>(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::sqrt(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&)::{lambda(int, modnum<1000000007>)#1}):
✗ Branch 271 → 272 not taken.
✓ Branch 271 → 273 taken 26 times.
✗ Branch 273 → 274 not taken.
✓ Branch 273 → 275 taken 26 times.
void dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> >::convolve_helper<dirichlet_series::operator/(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&)::{lambda(int, modnum<1000000007>)#1}>(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::operator/(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&)::{lambda(int, modnum<1000000007>)#1}):
✓ Branch 271 → 272 taken 24801 times.
✓ Branch 271 → 273 taken 46601 times.
✗ Branch 273 → 274 not taken.
✓ Branch 273 → 275 taken 46601 times.
void dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> >::convolve_helper<dirichlet_series::operator*(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&)::{lambda(int, modnum<1000000007>)#1}>(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::operator*(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&)::{lambda(int, modnum<1000000007>)#1}):
✓ Branch 271 → 272 taken 25057 times.
✓ Branch 271 → 273 taken 47118 times.
✗ Branch 273 → 274 not taken.
✓ Branch 273 → 275 taken 47118 times.
void dirichlet_series::prefix<dirichlet_series::test::layout, long>::convolve_helper<dirichlet_series::operator/(dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::prefix<dirichlet_series::test::layout, long> const&)::{lambda(int, long)#1}>(dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::operator/(dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::prefix<dirichlet_series::test::layout, long> const&)::{lambda(int, long)#1}):
✗ Branch 203 → 204 not taken.
✓ Branch 203 → 205 taken 26 times.
✗ Branch 205 → 206 not taken.
✓ Branch 205 → 207 taken 26 times.
void dirichlet_series::prefix<dirichlet_series::test::layout, long>::convolve_helper<dirichlet_series::operator*(dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::prefix<dirichlet_series::test::layout, long> const&)::{lambda(int, long)#1}>(dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::operator*(dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::prefix<dirichlet_series::test::layout, long> const&)::{lambda(int, long)#1}):
✗ Branch 203 → 204 not taken.
✓ Branch 203 → 205 taken 13 times.
✗ Branch 205 → 206 not taken.
✓ Branch 205 → 207 taken 13 times.
void dirichlet_series::prefix<main::layout, modnum<998244353> >::convolve_helper<dirichlet_series::operator/(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&)::{lambda(int, modnum<998244353>)#1}>(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::operator/(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&)::{lambda(int, modnum<998244353>)#1}):
✓ Branch 60 → 61 taken 65608508 times.
✓ Branch 60 → 62 taken 1297957252 times.
void dirichlet_series::prefix<main::layout, modnum<998244353> >::convolve_helper<dirichlet_series::operator*(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&)::{lambda(int, modnum<998244353>)#1}>(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::operator*(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&)::{lambda(int, modnum<998244353>)#1}):
✓ Branch 60 → 61 taken 51042484 times.
✓ Branch 60 → 62 taken 1119754464 times.
|
2534506350 | int zlo_idx = int(x <= rt_over_i ? x * i : layout.len - (N_over_i / x)); |
| 315 | 2534506350 | this->st[zlo_idx] += v; | |
| 316 | 2534506350 | tot_sub += v; | |
| 317 | } | ||
| 318 |
4/4void dirichlet_series::prefix<main::layout, modnum<998244353> >::convolve_helper<dirichlet_series::operator/(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&)::{lambda(int, modnum<998244353>)#1}>(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::operator/(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&)::{lambda(int, modnum<998244353>)#1}):
✓ Branch 67 → 68 taken 4543201 times.
✓ Branch 67 → 69 taken 8731087 times.
void dirichlet_series::prefix<main::layout, modnum<998244353> >::convolve_helper<dirichlet_series::operator*(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&)::{lambda(int, modnum<998244353>)#1}>(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::operator*(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&)::{lambda(int, modnum<998244353>)#1}):
✓ Branch 67 → 68 taken 3845093 times.
✓ Branch 67 → 69 taken 6344645 times.
|
23531050 | this->en[-(i-1)] -= tot_sub; |
| 319 | |||
| 320 | // Case 0b: x = y > 1 | ||
| 321 | { | ||
| 322 |
14/14void dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> >::convolve_helper<dirichlet_series::sqrt(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&)::{lambda(int, modnum<1000000007>)#1}>(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::sqrt(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&)::{lambda(int, modnum<1000000007>)#1}):
✓ Branch 295 → 296 taken 30 times.
✓ Branch 295 → 297 taken 110 times.
void dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> >::convolve_helper<dirichlet_series::operator/(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&)::{lambda(int, modnum<1000000007>)#1}>(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::operator/(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&)::{lambda(int, modnum<1000000007>)#1}):
✓ Branch 295 → 296 taken 4705 times.
✓ Branch 295 → 297 taken 28321 times.
void dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> >::convolve_helper<dirichlet_series::operator*(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&)::{lambda(int, modnum<1000000007>)#1}>(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::operator*(dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&, dirichlet_series::prefix<dirichlet_series::test::layout, modnum<1000000007> > const&)::{lambda(int, modnum<1000000007>)#1}):
✓ Branch 295 → 296 taken 4824 times.
✓ Branch 295 → 297 taken 28824 times.
void dirichlet_series::prefix<dirichlet_series::test::layout, long>::convolve_helper<dirichlet_series::operator/(dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::prefix<dirichlet_series::test::layout, long> const&)::{lambda(int, long)#1}>(dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::operator/(dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::prefix<dirichlet_series::test::layout, long> const&)::{lambda(int, long)#1}):
✓ Branch 234 → 235 taken 30 times.
✓ Branch 234 → 236 taken 110 times.
void dirichlet_series::prefix<dirichlet_series::test::layout, long>::convolve_helper<dirichlet_series::operator*(dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::prefix<dirichlet_series::test::layout, long> const&)::{lambda(int, long)#1}>(dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::operator*(dirichlet_series::prefix<dirichlet_series::test::layout, long> const&, dirichlet_series::prefix<dirichlet_series::test::layout, long> const&)::{lambda(int, long)#1}):
✓ Branch 234 → 235 taken 15 times.
✓ Branch 234 → 236 taken 55 times.
void dirichlet_series::prefix<main::layout, modnum<998244353> >::convolve_helper<dirichlet_series::operator/(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&)::{lambda(int, modnum<998244353>)#1}>(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::operator/(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&)::{lambda(int, modnum<998244353>)#1}):
✓ Branch 70 → 71 taken 214102 times.
✓ Branch 70 → 72 taken 13060186 times.
void dirichlet_series::prefix<main::layout, modnum<998244353> >::convolve_helper<dirichlet_series::operator*(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&)::{lambda(int, modnum<998244353>)#1}>(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::operator*(dirichlet_series::prefix<main::layout, modnum<998244353> > const&, dirichlet_series::prefix<main::layout, modnum<998244353> > const&)::{lambda(int, modnum<998244353>)#1}):
✓ Branch 70 → 71 taken 203162 times.
✓ Branch 70 → 72 taken 9986576 times.
|
23531050 | int zlo_idx = int(i <= rt_over_i ? i * i : layout.len - (N_over_i / i)); |
| 323 | 23531050 | this->st[zlo_idx] += ai * bi; | |
| 324 | } | ||
| 325 | } | ||
| 326 | } | ||
| 327 | 63267 | } | |
| 328 | |||
| 329 | public: | ||
| 330 | 31627 | friend prefix operator * (prefix const& a, prefix const& b) { | |
| 331 | 31627 | prefix r; | |
| 332 | 31627 | r.st[1] = a.st[1] * b.st[1]; | |
| 333 | 100291 | r.convolve_helper(a, b, [&](int i, T cur_sum) -> T { | |
| 334 |
8/8✓ Branch 2 → 3 taken 10196213 times.
✓ Branch 2 → 4 taken 10198419 times.
✓ Branch 5 → 6 taken 10199624 times.
✓ Branch 5 → 7 taken 10195008 times.
✓ Branch 8 → 9 taken 10198602 times.
✓ Branch 8 → 10 taken 10196030 times.
✓ Branch 11 → 12 taken 10199479 times.
✓ Branch 11 → 13 taken 10195153 times.
|
81647192 | return cur_sum + (a.st[i] - a.st[i-1]) * b.st[1] + a.st[1] * (b.st[i] - b.st[i-1]); |
| 335 | }); | ||
| 336 | 31627 | return r; | |
| 337 | } | ||
| 338 |
1/1✓ Branch 4 → 5 taken 84 times.
|
252 | prefix& operator *= (const prefix& o) { return *this = *this * o; } |
| 339 | |||
| 340 | ✗ | friend T get_conv_N(prefix const& a, prefix const& b) { | |
| 341 | ✗ | T ans = a.st[1] * b.en[-1]; | |
| 342 | ✗ | for (int i = 2; i <= layout.len; i++) { | |
| 343 | ✗ | ans += (a.st[i] - a.st[i-1]) * b.en[-i]; | |
| 344 | } | ||
| 345 | ✗ | return ans; | |
| 346 | } | ||
| 347 | |||
| 348 | 31580 | friend prefix operator / (prefix const& a, prefix const& b) { | |
| 349 | 31580 | prefix r; | |
| 350 | 31580 | T inv_b1 = inv(b.st[1]); | |
| 351 | 31580 | r.st[1] = a.st[1] * inv_b1; | |
| 352 | 99100 | r.convolve_helper(r, b, [&](int i, T cur_sum) -> T { | |
| 353 |
8/8✓ Branch 2 → 3 taken 10200501 times.
✓ Branch 2 → 4 taken 16363261 times.
✓ Branch 5 → 6 taken 17056558 times.
✓ Branch 5 → 7 taken 9507204 times.
✓ Branch 8 → 9 taken 20504008 times.
✓ Branch 8 → 10 taken 6059754 times.
✓ Branch 11 → 12 taken 16255453 times.
✓ Branch 11 → 13 taken 10308309 times.
|
106322568 | return (a.st[i] - (cur_sum + r.st[1] * (b.st[i] - b.st[i-1]))) * inv_b1 + r.st[i-1]; |
| 354 | }); | ||
| 355 | 31580 | return r; | |
| 356 | } | ||
| 357 | ✗ | prefix& operator /= (const prefix& o) { return *this = *this / o; } | |
| 358 | |||
| 359 | 60 | friend prefix sqrt(const prefix& a) { | |
| 360 | 60 | prefix r; | |
| 361 | // assert(a.st[1] == 1); | ||
| 362 | 120 | r.st[1] = 1; | |
| 363 | 180 | T inv_2 = inv(T(2)); | |
| 364 | 60 | r.convolve_helper(r, r, [&](int i, T cur_sum) -> T { | |
| 365 | 310 | return (a.st[i] - cur_sum) * inv_2 + r.st[i-1]; | |
| 366 | }); | ||
| 367 | 60 | return r; | |
| 368 | } | ||
| 369 | |||
| 370 | // This computes a pseudo-Euler transform of the sequence. | ||
| 371 | // | ||
| 372 | // Formally, given a Dirichlet series | ||
| 373 | // A = sum a_i / i^s, | ||
| 374 | // we output the Dirichlet series corresponding to | ||
| 375 | // B = prod 1 / (1 - a_i i^{-s}) | ||
| 376 | // | ||
| 377 | // Note: strictly speaking, the standard Euler transform over a generating function should be | ||
| 378 | // A = sum a_i / i^s -> B = prod 1 / (1 - i^{-s})^a_i | ||
| 379 | // but our defintion is better suited for totally multiplicative functions, | ||
| 380 | // and always works over general rings. Also, the two definitions match | ||
| 381 | // when the a_i are always 0/1. | ||
| 382 | // | ||
| 383 | // This runs in $O(n^{2/3})$ time, but requires small inverses (up to 1/120). | ||
| 384 | 12 | friend prefix euler_transform_fraction(prefix a_pref) { | |
| 385 | 12 | values<layout, T> a(std::move(a_pref)); | |
| 386 | // assert(a.st[1] == 0); | ||
| 387 | |||
| 388 | // Phase 0: stash away values up to the 6th root of N | ||
| 389 | int x; | ||
| 390 |
5/8✗ Branch 8 → 9 not taken.
✓ Branch 8 → 12 taken 17 times.
✗ Branch 14 → 15 not taken.
✓ Branch 14 → 16 taken 17 times.
✗ Branch 16 → 17 not taken.
✓ Branch 16 → 18 taken 17 times.
✓ Branch 18 → 5 taken 5 times.
✓ Branch 18 → 19 taken 12 times.
|
17 | for (x = 2; layout.rt / x / x / x > 0; x++) { } |
| 391 | |||
| 392 | // Phase 1: adjust the values and insert the necessary extra powers | ||
| 393 | 132 | std::array<T, 6> invs{T{}, T(1), inv(T(2)), inv(T(3)), inv(T(4)), inv(T(5))}; | |
| 394 |
2/2✓ Branch 97 → 69 taken 64 times.
✓ Branch 97 → 98 taken 12 times.
|
76 | for (int i = int(layout.rt); i >= x; i--) { |
| 395 | 64 | T v = a.st[i]; | |
| 396 | 64 | int e = 1; | |
| 397 | 64 | T pv = v; | |
| 398 | 64 | int64_t pi = i; | |
| 399 |
3/4✗ Branch 89 → 90 not taken.
✓ Branch 89 → 92 taken 152 times.
✓ Branch 93 → 76 taken 88 times.
✓ Branch 93 → 94 taken 64 times.
|
152 | while (pi <= layout.N/i) { |
| 400 | 88 | e++; | |
| 401 | 88 | pi *= i; | |
| 402 | 88 | pv *= v; | |
| 403 | 88 | a.st[layout.get_value_bucket(pi)] += pv * invs[e]; | |
| 404 | } | ||
| 405 | } | ||
| 406 | |||
| 407 | // Phase 2: now we take exp of the adjusted version | ||
| 408 | // In particular, we take e^a = 1 + a + a^2 / 2 + a^3 / 6 + a^4 / 24 + a^5 / 120 | ||
| 409 | 12 | prefix v; | |
| 410 |
2/2✓ Branch 117 → 102 taken 138 times.
✓ Branch 117 → 118 taken 12 times.
|
150 | for (int i = x; i < layout.len; i++) { |
| 411 | 138 | v.st[i] = v.st[i-1] + a.st[i]; | |
| 412 | } | ||
| 413 | |||
| 414 |
1/1✓ Branch 120 → 147 taken 12 times.
|
12 | prefix r = v * v; |
| 415 |
2/2✓ Branch 149 → 121 taken 138 times.
✓ Branch 149 → 150 taken 12 times.
|
150 | for (int i = x; i < layout.len; i++) { |
| 416 | 276 | r.st[i] = r.st[i] * invs[5] + v.st[i]; | |
| 417 | } | ||
| 418 |
1/1✓ Branch 150 → 177 taken 12 times.
|
12 | r *= v; |
| 419 |
2/2✓ Branch 179 → 151 taken 138 times.
✓ Branch 179 → 180 taken 12 times.
|
150 | for (int i = x; i < layout.len; i++) { |
| 420 | 276 | r.st[i] = r.st[i] * invs[4] + v.st[i]; | |
| 421 | } | ||
| 422 |
1/1✓ Branch 180 → 207 taken 12 times.
|
12 | r *= v; |
| 423 |
2/2✓ Branch 209 → 181 taken 138 times.
✓ Branch 209 → 210 taken 12 times.
|
150 | for (int i = x; i < layout.len; i++) { |
| 424 | 276 | r.st[i] = r.st[i] * invs[3] + v.st[i]; | |
| 425 | } | ||
| 426 |
1/1✓ Branch 210 → 237 taken 12 times.
|
12 | r *= v; |
| 427 |
2/2✓ Branch 239 → 211 taken 138 times.
✓ Branch 239 → 253 taken 12 times.
|
150 | for (int i = x; i < layout.len; i++) { |
| 428 | 276 | r.st[i] = r.st[i] * invs[2] + v.st[i]; | |
| 429 | } | ||
| 430 | |||
| 431 |
2/2✓ Branch 255 → 240 taken 155 times.
✓ Branch 255 → 256 taken 12 times.
|
167 | for (int i = 1; i < layout.len; i++) { |
| 432 | 310 | r.st[i] += T(1); | |
| 433 | } | ||
| 434 | |||
| 435 | // Phase 3: apply the extra below x | ||
| 436 |
2/2✓ Branch 295 → 257 taken 5 times.
✓ Branch 295 → 296 taken 12 times.
|
17 | for (x--; x >= 2; x--) { |
| 437 | 5 | T ax = a.st[x]; | |
| 438 |
1/2✗ Branch 269 → 270 not taken.
✓ Branch 269 → 290 taken 5 times.
|
10 | if (ax == 0) continue; |
| 439 |
2/2✓ Branch 292 → 271 taken 174 times.
✓ Branch 292 → 293 taken 5 times.
|
179 | for (int i = x; i < layout.len; i++) { |
| 440 |
1/2✗ Branch 275 → 276 not taken.
✓ Branch 275 → 277 taken 174 times.
|
174 | r.st[i] += r.st[layout.get_value_bucket(layout.get_bucket_bound(i) / x)] * ax; |
| 441 | } | ||
| 442 | } | ||
| 443 | |||
| 444 | 24 | return r; | |
| 445 | 24 | } | |
| 446 | |||
| 447 | // This computes the inverse of the pseudo-Euler transformation. See the | ||
| 448 | // comment on euler_transform() for more details. | ||
| 449 | 12 | friend prefix inverse_euler_transform_fraction(prefix a) { | |
| 450 | 12 | values<layout, T> r; | |
| 451 | |||
| 452 | // assert(a.st[1] == 1); | ||
| 453 | |||
| 454 | // Phase 1: manually eliminate values up to the 6th root of a | ||
| 455 | |||
| 456 | int x; | ||
| 457 |
5/8✗ Branch 69 → 70 not taken.
✓ Branch 69 → 73 taken 17 times.
✗ Branch 75 → 76 not taken.
✓ Branch 75 → 77 taken 17 times.
✗ Branch 77 → 78 not taken.
✓ Branch 77 → 79 taken 17 times.
✓ Branch 79 → 6 taken 5 times.
✓ Branch 79 → 93 taken 12 times.
|
17 | for (x = 2; layout.rt / x / x / x > 0; x++) { |
| 458 | 10 | T v = a.st[x] - T(1); | |
| 459 |
1/2✗ Branch 25 → 26 not taken.
✓ Branch 25 → 27 taken 5 times.
|
10 | if (v == 0) continue; // Small optimization, good for prime counting in particular |
| 460 | 5 | r.st[x] = v; | |
| 461 |
2/2✓ Branch 52 → 33 taken 169 times.
✓ Branch 52 → 53 taken 5 times.
|
174 | for (int i = layout.len - 1; i > x; i--) { |
| 462 |
1/2✗ Branch 37 → 38 not taken.
✓ Branch 37 → 39 taken 169 times.
|
169 | a.st[i] -= a.st[layout.get_value_bucket(layout.get_bucket_bound(i) / x)] * v; |
| 463 | } | ||
| 464 | 10 | a.st[x] = T(1); | |
| 465 | } | ||
| 466 | |||
| 467 |
2/2✓ Branch 93 → 80 taken 17 times.
✓ Branch 93 → 107 taken 12 times.
|
29 | for (int i = 1; i < x; i++) { |
| 468 | 34 | a.st[i] = T(); | |
| 469 | } | ||
| 470 |
2/2✓ Branch 109 → 94 taken 138 times.
✓ Branch 109 → 110 taken 12 times.
|
150 | for (int i = x; i < layout.len; i++) { |
| 471 | 276 | a.st[i] -= T(1); | |
| 472 | } | ||
| 473 | |||
| 474 | 132 | std::array<T, 6> invs{T{}, T(1), inv(T(2)), inv(T(3)), inv(T(4)), inv(T(5))}; | |
| 475 | |||
| 476 | // Phase 2: now we take log of the remaining thing, using just the first few terms. | ||
| 477 | // In particular, we take log_a = a^5 / 5 - a^4 / 4 + a^3 / 3 - a^2 / 2 + a | ||
| 478 | 12 | prefix log_a; | |
| 479 |
2/2✓ Branch 181 → 161 taken 138 times.
✓ Branch 181 → 182 taken 12 times.
|
150 | for (int i = x; i < layout.len; i++) { |
| 480 | 276 | log_a.st[i] = a.st[i] * invs[5]; | |
| 481 | } | ||
| 482 |
1/1✓ Branch 182 → 201 taken 12 times.
|
12 | log_a *= a; |
| 483 |
2/2✓ Branch 203 → 183 taken 138 times.
✓ Branch 203 → 204 taken 12 times.
|
150 | for (int i = x; i < layout.len; i++) { |
| 484 | 276 | log_a.st[i] -= a.st[i] * invs[4]; | |
| 485 | } | ||
| 486 |
1/1✓ Branch 204 → 223 taken 12 times.
|
12 | log_a *= a; |
| 487 |
2/2✓ Branch 225 → 205 taken 138 times.
✓ Branch 225 → 226 taken 12 times.
|
150 | for (int i = x; i < layout.len; i++) { |
| 488 | 276 | log_a.st[i] += a.st[i] * invs[3]; | |
| 489 | } | ||
| 490 |
1/1✓ Branch 226 → 245 taken 12 times.
|
12 | log_a *= a; |
| 491 |
2/2✓ Branch 247 → 227 taken 138 times.
✓ Branch 247 → 248 taken 12 times.
|
150 | for (int i = x; i < layout.len; i++) { |
| 492 | 276 | log_a.st[i] -= a.st[i] * invs[2]; | |
| 493 | } | ||
| 494 |
1/1✓ Branch 248 → 267 taken 12 times.
|
12 | log_a *= a; |
| 495 |
2/2✓ Branch 269 → 249 taken 138 times.
✓ Branch 269 → 283 taken 12 times.
|
150 | for (int i = x; i < layout.len; i++) { |
| 496 | 276 | log_a.st[i] += a.st[i] * invs[1]; | |
| 497 | } | ||
| 498 | |||
| 499 | // Phase 3: correct log_a; we need to get rid of the extra powers. | ||
| 500 |
2/2✓ Branch 285 → 270 taken 138 times.
✓ Branch 285 → 314 taken 12 times.
|
150 | for (int i = x; i < layout.len; i++) { |
| 501 | 138 | r.st[i] = log_a.st[i] - log_a.st[i-1]; | |
| 502 | } | ||
| 503 |
2/2✓ Branch 316 → 286 taken 64 times.
✓ Branch 316 → 317 taken 12 times.
|
76 | for (; x <= layout.rt; x++) { |
| 504 | 64 | T v = r.st[x]; | |
| 505 | 64 | int e = 1; | |
| 506 | 64 | T pv = v; | |
| 507 | 64 | int64_t px = x; | |
| 508 |
3/4✗ Branch 306 → 307 not taken.
✓ Branch 306 → 309 taken 152 times.
✓ Branch 310 → 293 taken 88 times.
✓ Branch 310 → 311 taken 64 times.
|
152 | while (px <= layout.N/x) { |
| 509 | 88 | e++; | |
| 510 | 88 | px *= x; | |
| 511 | 88 | pv *= v; | |
| 512 | 88 | r.st[layout.get_value_bucket(px)] -= pv * invs[e]; | |
| 513 | } | ||
| 514 | } | ||
| 515 | |||
| 516 | 24 | return prefix(std::move(r)); | |
| 517 | 24 | } | |
| 518 | |||
| 519 | 12 | friend prefix euler_transform_binary_indexed_tree(prefix a_pref) { | |
| 520 | 12 | int x = 2; | |
| 521 |
4/6✗ Branch 5 → 6 not taken.
✓ Branch 5 → 8 taken 33 times.
✗ Branch 9 → 10 not taken.
✓ Branch 9 → 11 taken 33 times.
✓ Branch 11 → 3 taken 21 times.
✓ Branch 11 → 12 taken 12 times.
|
33 | while (x <= layout.N / x / x) x++; |
| 522 | |||
| 523 | 12 | prefix r_pref; | |
| 524 |
2/2✓ Branch 35 → 16 taken 122 times.
✓ Branch 35 → 105 taken 12 times.
|
134 | for (int i = x; i < layout.len; i++) { |
| 525 | 122 | r_pref.st[i] = a_pref.st[i] - a_pref.st[x-1]; | |
| 526 | } | ||
| 527 | |||
| 528 |
2/2✓ Branch 107 → 36 taken 48 times.
✓ Branch 107 → 108 taken 12 times.
|
60 | for (int i = x; i <= layout.rt; i++) { |
| 529 | 48 | T vi = a_pref.st[i] - a_pref.st[i-1]; | |
| 530 |
2/2✓ Branch 53 → 54 taken 28 times.
✓ Branch 53 → 55 taken 20 times.
|
96 | if (vi == 0) continue; |
| 531 | |||
| 532 |
1/2✗ Branch 56 → 57 not taken.
✓ Branch 56 → 59 taken 20 times.
|
20 | int64_t N_over_i = layout.N / i; |
| 533 |
1/2✗ Branch 62 → 63 not taken.
✓ Branch 62 → 66 taken 20 times.
|
20 | int64_t rt_over_i = layout.rt / i; |
| 534 |
1/2✗ Branch 68 → 69 not taken.
✓ Branch 68 → 70 taken 20 times.
|
20 | int64_t max_z = N_over_i / i; |
| 535 |
2/2✓ Branch 102 → 71 taken 48 times.
✓ Branch 102 → 103 taken 20 times.
|
68 | for (int z = 1; z <= max_z; z++) { |
| 536 | 48 | int jlo_idx = i-1; | |
| 537 |
3/4✓ Branch 71 → 72 taken 24 times.
✓ Branch 71 → 75 taken 24 times.
✗ Branch 75 → 76 not taken.
✓ Branch 75 → 77 taken 24 times.
|
48 | int jhi_idx = int(z <= rt_over_i ? layout.len - i * z : N_over_i / z); |
| 538 | 48 | assert(jlo_idx < jhi_idx); | |
| 539 | 48 | T v = vi * (a_pref.st[jhi_idx] - a_pref.st[jlo_idx]); | |
| 540 | 48 | r_pref.st[layout.len-z] += v; | |
| 541 | } | ||
| 542 | } | ||
| 543 | |||
| 544 | 12 | bit<layout, T> r(std::move(r_pref)); | |
| 545 | 24 | r.increment_bucket_suffix(1, T(1)); | |
| 546 |
2/2✓ Branch 139 → 117 taken 21 times.
✓ Branch 139 → 140 taken 12 times.
|
33 | for (int i = x-1; i >= 2; i--) { |
| 547 | 21 | T cur = a_pref.st[i] - a_pref.st[i-1]; | |
| 548 |
2/2✓ Branch 134 → 135 taken 8 times.
✓ Branch 134 → 136 taken 13 times.
|
42 | if (cur == 0) continue; |
| 549 | 13 | r.sparse_mul_unlimited(i, cur); | |
| 550 | } | ||
| 551 |
1/1✓ Branch 142 → 143 taken 12 times.
|
24 | return prefix(std::move(r)); |
| 552 | 12 | } | |
| 553 | |||
| 554 | 12 | friend prefix inverse_euler_transform_binary_indexed_tree(prefix a_pref) { | |
| 555 | // assert(a_pref.st[1] == 1); | ||
| 556 | |||
| 557 | 12 | bit<layout, T> a_bit(std::move(a_pref)); | |
| 558 | 12 | values<layout, T> r; | |
| 559 | |||
| 560 | // First, use the BIT to clear up to N^1/3 | ||
| 561 | int x; | ||
| 562 |
4/6✗ Branch 36 → 37 not taken.
✓ Branch 36 → 39 taken 33 times.
✗ Branch 40 → 41 not taken.
✓ Branch 40 → 42 taken 33 times.
✓ Branch 42 → 8 taken 21 times.
✓ Branch 42 → 43 taken 12 times.
|
33 | for (x = 2; x <= layout.N / x / x; x++) { |
| 563 | 42 | T cur = a_bit.get_bucket_prefix(x) - T(1); | |
| 564 |
2/2✓ Branch 27 → 28 taken 8 times.
✓ Branch 27 → 29 taken 13 times.
|
42 | if (cur == 0) continue; |
| 565 | 13 | r.st[x] = cur; | |
| 566 | 13 | a_bit.sparse_div_unlimited(x, cur); | |
| 567 | } | ||
| 568 |
1/1✓ Branch 44 → 45 taken 12 times.
|
24 | a_pref = prefix<layout, T>(std::move(a_bit)); |
| 569 | |||
| 570 | // Now, a_pref contains terms of the form r[i] or r[i] * r[j], so let's | ||
| 571 | // subtract out the semiprimes. | ||
| 572 | // Note that N^1/3 < x <= i <= j, so N/i/j <= N^1/3 < x | ||
| 573 | |||
| 574 |
2/2✓ Branch 77 → 60 taken 122 times.
✓ Branch 77 → 145 taken 12 times.
|
134 | for (int i = x; i < layout.len; i++) { |
| 575 | 122 | T vi = a_pref.st[i] - a_pref.st[i-1]; | |
| 576 | 122 | r.st[i] = vi; | |
| 577 | } | ||
| 578 | |||
| 579 | // We want i <= j <= N/i/z | ||
| 580 |
2/2✓ Branch 147 → 78 taken 48 times.
✓ Branch 147 → 148 taken 12 times.
|
60 | for (int i = x; i <= layout.rt; i++) { |
| 581 | 48 | T vi = r.st[i]; | |
| 582 |
2/2✓ Branch 90 → 91 taken 28 times.
✓ Branch 90 → 92 taken 20 times.
|
96 | if (vi == 0) continue; |
| 583 | |||
| 584 |
1/2✗ Branch 93 → 94 not taken.
✓ Branch 93 → 96 taken 20 times.
|
20 | int64_t N_over_i = layout.N / i; |
| 585 |
1/2✗ Branch 99 → 100 not taken.
✓ Branch 99 → 103 taken 20 times.
|
20 | int64_t rt_over_i = layout.rt / i; |
| 586 |
1/2✗ Branch 105 → 106 not taken.
✓ Branch 105 → 107 taken 20 times.
|
20 | int64_t max_z = N_over_i / i; |
| 587 |
2/2✓ Branch 142 → 108 taken 48 times.
✓ Branch 142 → 143 taken 20 times.
|
68 | for (int z = 1; z <= max_z; z++) { |
| 588 | 48 | int jlo_idx = i-1; | |
| 589 |
3/4✓ Branch 108 → 109 taken 24 times.
✓ Branch 108 → 112 taken 24 times.
✗ Branch 112 → 113 not taken.
✓ Branch 112 → 114 taken 24 times.
|
48 | int jhi_idx = int(z <= rt_over_i ? layout.len - i * z : N_over_i / z); |
| 590 | 48 | assert(jlo_idx < jhi_idx); | |
| 591 | 48 | T v = vi * (a_pref.st[jhi_idx] - a_pref.st[jlo_idx]); | |
| 592 | 48 | r.en[-z] -= v; | |
| 593 |
1/2✓ Branch 135 → 136 taken 48 times.
✗ Branch 135 → 140 not taken.
|
48 | if (z > 0) r.en[-(z-1)] += v; |
| 594 | } | ||
| 595 | } | ||
| 596 | |||
| 597 | 24 | return prefix(std::move(r)); | |
| 598 | } | ||
| 599 | }; | ||
| 600 | |||
| 601 | // TODO: This will be useful for sparse convolution, which is nice for e.g. exp/log/prime counting | ||
| 602 | 2804 | template <div_vector_layout const& layout, typename T> class bit : public div_vector<layout, T>, public vectorspace_mixin<layout, T, bit<layout, T>> { | |
| 603 | public: | ||
| 604 | ✗ | bit() = default; | |
| 605 | |||
| 606 | ✗ | template <typename U> explicit bit(bit<layout, U> const& o) { | |
| 607 | ✗ | for (int i = 1; i < layout.len; i++) { | |
| 608 | ✗ | this->st[i] = T(o.st[i]); | |
| 609 | } | ||
| 610 | } | ||
| 611 | |||
| 612 | 24 | explicit bit(prefix<layout, T> && o) : div_vector<layout, T>(static_cast<div_vector<layout, T>&&>(std::move(o))) { | |
| 613 |
2/2✓ Branch 21 → 11 taken 310 times.
✓ Branch 21 → 22 taken 24 times.
|
334 | for (int i = layout.len - 1; i >= 1; i--) { |
| 614 | 310 | this->st[i] -= this->st[i & (i-1)]; | |
| 615 | } | ||
| 616 | 24 | } | |
| 617 | 2780 | explicit bit(prefix<layout, T> const& o) { | |
| 618 |
2/2✓ Branch 26 → 8 taken 136580 times.
✓ Branch 26 → 27 taken 2780 times.
|
139360 | for (int i = layout.len - 1; i >= 1; i--) { |
| 619 | 136580 | this->st[i] = o.st[i] - o.st[i & (i-1)]; | |
| 620 | } | ||
| 621 | 2780 | } | |
| 622 | 24 | explicit operator prefix<layout, T> () && { | |
| 623 | 24 | prefix<layout, T> r; | |
| 624 | 24 | swap(static_cast<div_vector<layout, T>&>(r), static_cast<div_vector<layout, T>&>(*this)); | |
| 625 |
2/2✓ Branch 23 → 10 taken 310 times.
✓ Branch 23 → 24 taken 24 times.
|
334 | for (int i = 1; i < layout.len; i++) { |
| 626 | 310 | r.st[i] += r.st[i & (i-1)]; | |
| 627 | } | ||
| 628 | 24 | return r; | |
| 629 | } | ||
| 630 | 2780 | explicit operator prefix<layout, T> () const& { | |
| 631 | 2780 | prefix<layout, T> r; | |
| 632 |
2/2✓ Branch 27 → 6 taken 136580 times.
✓ Branch 27 → 28 taken 2780 times.
|
139360 | for (int i = 1; i < layout.len; i++) { |
| 633 | 136580 | r.st[i] = this->st[i] + r.st[i & (i-1)]; | |
| 634 | } | ||
| 635 | 2780 | return r; | |
| 636 | } | ||
| 637 | |||
| 638 | 8595 | T get_bucket_prefix(int a) const { | |
| 639 | 17190 | T r = T(); | |
| 640 |
2/2✓ Branch 13 → 7 taken 10755 times.
✓ Branch 13 → 14 taken 8595 times.
|
19350 | for (; a > 0; a -= a & -a) { |
| 641 | 10755 | r += this->st[a]; | |
| 642 | } | ||
| 643 | 8595 | return r; | |
| 644 | } | ||
| 645 | ✗ | T get_prefix(int64_t v) const { | |
| 646 | ✗ | return get_bucket_prefix(layout.get_value_bucket(v)); | |
| 647 | } | ||
| 648 | 7097 | void increment_bucket_suffix(int a, T d) { | |
| 649 |
2/2✓ Branch 12 → 3 taken 11486 times.
✓ Branch 12 → 13 taken 7097 times.
|
18583 | for (; a < layout.len; a += a & -a) { |
| 650 | 11486 | this->st[a] += d; | |
| 651 | } | ||
| 652 | 7097 | } | |
| 653 | ✗ | void increment_suffix(int64_t v, T d) const { | |
| 654 | ✗ | return increment_bucket_suffix(layout.get_value_bucket(v), d); | |
| 655 | } | ||
| 656 | |||
| 657 | // These 4 functions facilitate some simple sparse convolution. | ||
| 658 | // They each take O(sqrt(N/x) log(N)) time. | ||
| 659 | |||
| 660 | // multiply by (1 + w x^s) | ||
| 661 | 1403 | void sparse_mul_at_most_one(int64_t x, T w) { | |
| 662 | 1403 | assert(x > 1); | |
| 663 | 1403 | int64_t j = 1; | |
| 664 |
4/6✗ Branch 8 → 9 not taken.
✓ Branch 8 → 12 taken 1403 times.
✓ Branch 14 → 15 taken 82 times.
✓ Branch 14 → 18 taken 1321 times.
✗ Branch 19 → 20 not taken.
✓ Branch 19 → 22 taken 1321 times.
|
1403 | T cur = get_bucket_prefix(int(j <= layout.rt / x ? layout.len - j * x : layout.N / x / j)); |
| 665 |
4/6✗ Branch 62 → 63 not taken.
✓ Branch 62 → 65 taken 2219 times.
✗ Branch 66 → 67 not taken.
✓ Branch 66 → 68 taken 2219 times.
✓ Branch 68 → 25 taken 816 times.
✓ Branch 68 → 69 taken 1403 times.
|
2219 | for (; (j+1) <= layout.N / x / (j+1); j++) { |
| 666 |
5/8✗ Branch 29 → 30 not taken.
✓ Branch 29 → 33 taken 816 times.
✓ Branch 35 → 36 taken 128 times.
✓ Branch 35 → 39 taken 688 times.
✗ Branch 40 → 41 not taken.
✓ Branch 40 → 43 taken 688 times.
✗ Branch 44 → 45 not taken.
✓ Branch 44 → 46 taken 688 times.
|
816 | T nxt = get_bucket_prefix(int(j + 1 <= layout.rt / x ? layout.len - (j+1) * x : layout.N / x / (j+1))); |
| 667 |
2/2✓ Branch 49 → 50 taken 809 times.
✓ Branch 49 → 60 taken 7 times.
|
816 | if (cur != nxt) { |
| 668 | 809 | increment_bucket_suffix(int(layout.len - j), w * (cur - nxt)); | |
| 669 | 809 | cur = nxt; | |
| 670 | } | ||
| 671 | } | ||
| 672 |
3/4✗ Branch 71 → 72 not taken.
✓ Branch 71 → 73 taken 1403 times.
✓ Branch 108 → 74 taken 2840 times.
✓ Branch 108 → 109 taken 1403 times.
|
4243 | for (int64_t i = layout.N / x / j; i > 0; i--) { |
| 673 | 2840 | T nxt = get_bucket_prefix(int(i-1)); | |
| 674 |
2/2✓ Branch 78 → 79 taken 2804 times.
✓ Branch 78 → 107 taken 36 times.
|
2840 | if (cur != nxt) { |
| 675 |
5/8✗ Branch 86 → 87 not taken.
✓ Branch 86 → 90 taken 2804 times.
✓ Branch 92 → 93 taken 195 times.
✓ Branch 92 → 94 taken 2609 times.
✗ Branch 95 → 96 not taken.
✓ Branch 95 → 98 taken 2609 times.
✗ Branch 99 → 100 not taken.
✓ Branch 99 → 101 taken 2609 times.
|
2804 | increment_bucket_suffix(int(i <= layout.rt / x ? i * x : layout.len - layout.N / x / i), w * (cur - nxt)); |
| 676 | 2804 | cur = nxt; | |
| 677 | } | ||
| 678 | } | ||
| 679 | 1403 | } | |
| 680 | |||
| 681 | // multiply by 1/(1 - w x^s) = 1 + wx^s + w^2 (x^2)^s + ... | ||
| 682 | 1403 | void sparse_mul_unlimited(int64_t x, T w) { | |
| 683 | 1403 | assert(x > 1); | |
| 684 | 1403 | T prv = T(); | |
| 685 | int64_t i; | ||
| 686 |
4/6✗ Branch 45 → 46 not taken.
✓ Branch 45 → 48 taken 3610 times.
✗ Branch 49 → 50 not taken.
✓ Branch 49 → 51 taken 3610 times.
✓ Branch 51 → 9 taken 2207 times.
✓ Branch 51 → 52 taken 1403 times.
|
3610 | for (i = 1; i <= layout.N / x / i; i++) { |
| 687 | 2207 | T cur = get_bucket_prefix(int(i)); | |
| 688 |
2/2✓ Branch 13 → 14 taken 2175 times.
✓ Branch 13 → 42 taken 32 times.
|
2207 | if (cur != prv) { |
| 689 |
5/8✗ Branch 21 → 22 not taken.
✓ Branch 21 → 25 taken 2175 times.
✓ Branch 27 → 28 taken 195 times.
✓ Branch 27 → 29 taken 1980 times.
✗ Branch 30 → 31 not taken.
✓ Branch 30 → 33 taken 1980 times.
✗ Branch 34 → 35 not taken.
✓ Branch 34 → 36 taken 1980 times.
|
2175 | increment_bucket_suffix(int(i <= layout.rt / x ? i * x : layout.len - layout.N / x / i), w * (cur - prv)); |
| 690 | 2175 | prv = cur; | |
| 691 | } | ||
| 692 | } | ||
| 693 |
2/2✓ Branch 91 → 54 taken 1308 times.
✓ Branch 91 → 92 taken 1403 times.
|
2711 | for (int64_t j = layout.N / x / i; j >= 1; j--) { |
| 694 |
5/8✗ Branch 58 → 59 not taken.
✓ Branch 58 → 62 taken 1308 times.
✓ Branch 64 → 65 taken 210 times.
✓ Branch 64 → 68 taken 1098 times.
✗ Branch 69 → 70 not taken.
✓ Branch 69 → 72 taken 1098 times.
✗ Branch 73 → 74 not taken.
✓ Branch 73 → 75 taken 1098 times.
|
1308 | T cur = get_bucket_prefix(int(j <= layout.rt / x ? layout.len - j * x : layout.N / x / j)); |
| 695 |
2/2✓ Branch 78 → 79 taken 1297 times.
✓ Branch 78 → 89 taken 11 times.
|
1308 | if (cur != prv) { |
| 696 | 1297 | increment_bucket_suffix(int(layout.len - j), w * (cur - prv)); | |
| 697 | 1297 | prv = cur; | |
| 698 | } | ||
| 699 | } | ||
| 700 | 1403 | } | |
| 701 | |||
| 702 | // divide by (1 + w x^s) | ||
| 703 | 1390 | void sparse_div_at_most_one(int64_t x, T w) { | |
| 704 | 2780 | return sparse_mul_unlimited(x, -w); | |
| 705 | } | ||
| 706 | |||
| 707 | // divide by 1/(1 - w x^s) = 1 + wx^s + w^2 (x^2)^s + ... | ||
| 708 | 13 | void sparse_div_unlimited(int64_t x, T w) { | |
| 709 | 26 | return sparse_mul_at_most_one(x, -w); | |
| 710 | } | ||
| 711 | }; | ||
| 712 | |||
| 713 | } | ||
| 714 |