fft/bm.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include <bits/stdc++.h> | ||
| 4 | |||
| 5 | namespace wala { | ||
| 6 | |||
| 7 | template <typename num> | ||
| 8 | 1 | std::vector<num> BerlekampMassey(const std::vector<num>& s) { | |
| 9 | 1 | int n = int(s.size()), L = 0, m = 0; | |
| 10 |
2/2✓ Branch 9 → 10 taken 1 time.
✓ Branch 13 → 14 taken 1 time.
|
1 | std::vector<num> C(n), B(n), T; |
| 11 | 2 | C[0] = B[0] = 1; | |
| 12 | |||
| 13 | 1 | num b = 1; | |
| 14 |
2/2✓ Branch 89 → 37 taken 8 times.
✓ Branch 89 → 90 taken 1 time.
|
9 | for (int i = 0; i < n; i++) { ++m; |
| 15 | 8 | num d = s[i]; | |
| 16 |
2/2✓ Branch 55 → 44 taken 12 times.
✓ Branch 55 → 56 taken 8 times.
|
20 | for (int j = 1; j <= L; j++) d += C[j] * s[i - j]; |
| 17 |
2/2✓ Branch 63 → 64 taken 6 times.
✓ Branch 63 → 65 taken 2 times.
|
17 | if (d == 0) continue; |
| 18 |
1/1✓ Branch 65 → 66 taken 2 times.
|
2 | T = C; num coef = d / b; |
| 19 |
2/2✓ Branch 80 → 69 taken 13 times.
✓ Branch 80 → 81 taken 2 times.
|
15 | for (int j = m; j < n; j++) C[j] -= coef * B[j - m]; |
| 20 |
2/2✓ Branch 81 → 82 taken 1 time.
✓ Branch 81 → 83 taken 1 time.
|
2 | if (2 * L > i) continue; |
| 21 |
1/1✓ Branch 83 → 84 taken 1 time.
|
1 | L = i + 1 - L; B = T; b = d; m = 0; |
| 22 | } | ||
| 23 | |||
| 24 |
2/2✓ Branch 90 → 91 taken 1 time.
✓ Branch 107 → 108 taken 1 time.
|
5 | C.resize(L + 1); C.erase(C.begin()); |
| 25 |
2/2✓ Branch 163 → 142 taken 2 times.
✓ Branch 163 → 164 taken 1 time.
|
7 | for (auto& x : C) { |
| 26 | 4 | x = -x; | |
| 27 | } | ||
| 28 | 2 | return C; | |
| 29 | 2 | } | |
| 30 | |||
| 31 | template <typename num> | ||
| 32 | 1 | num linearRec(const std::vector<num>& S, const std::vector<num>& tr, int64_t k) { | |
| 33 | 1 | int n = int(tr.size()); | |
| 34 | 1 | assert(S.size() >= tr.size()); | |
| 35 | |||
| 36 | 1 | auto combine = [&](std::vector<num> a, std::vector<num> b, bool e = false) { | |
| 37 | // multiply a * b * x^e | ||
| 38 |
1/1✓ Branch 9 → 10 taken 10 times.
|
10 | std::vector<num> res(int(a.size()) + int(b.size())); |
| 39 |
2/2✓ Branch 33 → 25 taken 20 times.
✓ Branch 33 → 34 taken 10 times.
|
30 | for (int i = 0; i < int(a.size()); i++) { |
| 40 |
2/2✓ Branch 28 → 12 taken 40 times.
✓ Branch 28 → 29 taken 20 times.
|
60 | for (int j = 0; j < int(b.size()); j++) { |
| 41 | 40 | res[i + j + e] += a[i] * b[j]; | |
| 42 | } | ||
| 43 | } | ||
| 44 |
2/2✓ Branch 65 → 55 taken 20 times.
✓ Branch 65 → 66 taken 10 times.
|
30 | for (int i = int(res.size())-1; i >= n; --i) { |
| 45 |
2/2✓ Branch 59 → 38 taken 40 times.
✓ Branch 59 → 60 taken 20 times.
|
60 | for (int j = 0; j < n; j++) { |
| 46 | 40 | res[i - 1 - j] += res[i] * tr[j]; | |
| 47 | } | ||
| 48 | } | ||
| 49 |
1/1✓ Branch 70 → 71 taken 10 times.
|
10 | res.resize(n); |
| 50 | 10 | return res; | |
| 51 | ✗ | }; | |
| 52 | |||
| 53 |
1/1✓ Branch 26 → 27 taken 1 time.
|
1 | std::vector<num> pol(n); |
| 54 |
1/2✓ Branch 28 → 29 taken 1 time.
✗ Branch 28 → 39 not taken.
|
2 | if (n > 0) pol[0] = num(1); |
| 55 | |||
| 56 | 1 | assert(k >= 0); | |
| 57 |
3/4✓ Branch 41 → 42 taken 1 time.
✗ Branch 41 → 100 not taken.
✓ Branch 101 → 43 taken 10 times.
✓ Branch 101 → 102 taken 1 time.
|
12 | for (int i = 64 - 1 - (k == 0 ? 64 : __builtin_clzll(k)); i >= 0; i--) { |
| 58 |
3/3✓ Branch 45 → 46 taken 10 times.
✓ Branch 47 → 48 taken 10 times.
✓ Branch 48 → 49 taken 10 times.
|
40 | pol = combine(pol, pol, (k >> i) & 1); |
| 59 | } | ||
| 60 | |||
| 61 | 1 | num res = 0; | |
| 62 |
2/2✓ Branch 118 → 107 taken 2 times.
✓ Branch 118 → 119 taken 1 time.
|
3 | for (int i = 0; i < n; i++) res += pol[i] * S[i]; |
| 63 | 2 | return res; | |
| 64 | 1 | } | |
| 65 | |||
| 66 | } // namespace wala | ||
| 67 |