GCC Code Coverage Report

Directory: ./
Coverage: low: ≥ 0% medium: ≥ 75.0% high: ≥ 90.0%
Coverage Exec / Excl / Total
Lines: 100.0% 36 / 0 / 36
Functions: 100.0% 4 / 0 / 4
Branches: 81.2% 39 / 0 / 48
src/comb/exlucas/lib.hpp
Line Branch Exec Source
1 #pragma once
2
3 #include "../../math/iroot/sqrt/lib.hpp"
4 #include "../../math/qpow/mod/lib.hpp"
5 #include "../../nt/crt/basic/lib.hpp"
6 #include "../seq/invseq/lib.hpp"
7
8 namespace tifa_libs {
9
10 // Calculate $\binom{m}{n} \bmod p$, p can be ANY INTEGER
11 class exlucas {
12 struct TIFA {
13 cu32 p, q;
14 const bool no_proot;
15 u64 m_;
16 vecuu facp, ifacp;
17
4/4
✓ Branch 0 taken 18 times.
✓ Branch 1 taken 71 times.
✓ Branch 2 taken 7 times.
✓ Branch 3 taken 11 times.
 89 CEXP TIFA(u32 p, u32 q) NE : p(p), q(q), no_proot(p == 2 && q >= 3) {
18
2/4
✓ Branch 0 taken 89 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 89 times.
✗ Branch 3 not taken.
 89 assert(p <= 100'000'000 && q > 0), m_ = 1;
19
3/4
✗ Branch 0 not taken.
✓ Branch 1 taken 150 times.
✓ Branch 3 taken 150 times.
✓ Branch 4 taken 89 times.
 239 while (q--) (m_ *= p), assert(m_ <= 100'000'000);
20 89 facp.resize(m_), facp[0] = facp[1] = 1;
21
2/2
✓ Branch 0 taken 3184001 times.
✓ Branch 1 taken 89 times.
 3184090 flt_ (u64, i, 2, m_)
22
2/2
✓ Branch 0 taken 524382 times.
✓ Branch 1 taken 2659619 times.
 3184001 if (i % p == 0) facp[i] = facp[i - 1], facp[i + 1] = facp[i - 1] * (i + 1) % m_, ++i;
23 2659619 else facp[i] = facp[i - 1] * i % m_;
24 89 ifacp = gen_invseq(facp, m_);
25 89 }
26 17000036 CEXP u64 operator()(i64 m, i64 n) CNE {
27
2/4
✓ Branch 0 taken 17000036 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 17000036 times.
 17000036 retif_((m < n || n < 0) [[unlikely]], 0);
28 17000036 i64 r = m - n;
29 17000036 i32 e0 = 0, eq = 0;
30 17000036 u32 i = 0;
31 17000036 u64 res = 1;
32
2/2
✓ Branch 0 taken 93436136 times.
✓ Branch 1 taken 5507647 times.
 98943783 while (m) {
33 93436136 res = res * facp[(u64)m % m_] % m_ * ifacp[(u64)n % m_] % m_ * ifacp[(u64)r % m_] % m_, m /= p, n /= p, r /= p;
34
2/2
✓ Branch 0 taken 11492389 times.
✓ Branch 1 taken 81943747 times.
 93436136 if (ci32 eps = (i32)(m - n - r); (e0 += eps) >= (i32)q) return 0;
35
2/2
✓ Branch 0 taken 69960497 times.
✓ Branch 1 taken 11983250 times.
 81943747 else if (++i >= q) eq += eps;
36 }
37
4/4
✓ Branch 0 taken 4876301 times.
✓ Branch 1 taken 631346 times.
✓ Branch 2 taken 64349 times.
✓ Branch 3 taken 4811952 times.
 5507647 cu64 _ = (!no_proot && (eq & 1) ? m_ - res : res) * qpow_mod(p, (u32)e0, m_) % m_;
38 5507647 return _;
39 }
40 };
41 cu32 m_;
42 vecuu ms;
43 vec<TIFA> cs;
44
45 public:
46 29 CEXPE exlucas(u32 md) NE : m_(md) {
47
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 29 times.
 29 assert(md < 100'000'000);
48
2/2
✓ Branch 1 taken 18736 times.
✓ Branch 2 taken 29 times.
 18765 flt_ (u32, i, 2, isqrt(md) + 1)
49
2/2
✓ Branch 0 taken 73 times.
✓ Branch 1 taken 18663 times.
 18736 if (md % i == 0) {
50 73 u32 j = 0, k = 1;
51
2/2
✓ Branch 0 taken 134 times.
✓ Branch 1 taken 73 times.
 207 while (md % i == 0) md /= i, ++j, k *= i;
52 73 ms.push_back(k), cs.emplace_back(i, j);
53 }
54
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 13 times.
 29 if (md > 1) ms.push_back(md), cs.emplace_back(md, 1);
55 29 }
56
57 5400014 CEXP u64 operator()(i64 m, i64 n) CNE {
58
3/6
✓ Branch 0 taken 5400014 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 5400014 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✓ Branch 5 taken 5400014 times.
 5400014 retif_((m_ == 1 || m < n || n < 0) [[unlikely]], 0);
59 5400014 vecii b;
60
2/2
✓ Branch 9 taken 17000036 times.
✓ Branch 10 taken 5400014 times.
 22400050 for (b.reserve(cs.size()); auto CR i : cs) b.push_back((i64)i(m, n));
61 5400014 return crt(b, ms)->first;
62 5400014 }
63 };
64
65 } // namespace tifa_libs
66