GCC Code Coverage Report


Directory: ./
Coverage: low: ≥ 0% medium: ≥ 75.0% high: ≥ 90.0%
Coverage Exec / Excl / Total
Lines: 100.0% 102 / 0 / 102
Functions: 100.0% 11 / 0 / 11
Branches: 95.8% 46 / 0 / 48

src/comb/seq/invseq/lib.hpp
Line Branch Exec Source
1 #pragma once
2
3 #include "../../../math/mul_mod/lib.hpp"
4 #include "../../../nt/inverse/lib.hpp"
5
6 namespace tifa_libs {
7
8 // i^{-1} for i in v
9 357 CEXP vecuu gen_invseq(spnuu v, u64 mod) NE {
10 357 cu32 n = (u32)v.size();
11
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 357 times.
357 retif_((n == 0) [[unlikely]], {});
12
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 357 times.
357 if (n == 1) return {inverse(v[0], mod)};
13 357 vecuu ans(n);
14 357 ans[0] = v[0];
15
2/2
✓ Branch 4 taken 912307604 times.
✓ Branch 5 taken 357 times.
912307961 flt_ (u32, i, 1, n) ans[i] = mul_mod_u(ans[i - 1], v[i], mod);
16 357 u64 _ = inverse(ans.back(), mod);
17
2/2
✓ Branch 5 taken 912307604 times.
✓ Branch 6 taken 357 times.
912307961 for (u32 i = n - 1; i; --i) ans[i] = mul_mod_u(_, ans[i - 1], mod), _ = mul_mod_u(_, v[i], mod);
18 357 ans[0] = _;
19 357 return ans;
20 357 }
21 // i^{-1} for i in v
22 template <class mint>
23 268 CEXP vec<mint> gen_invseq(vec<mint> CR v) NE {
24 268 u32 n = (u32)v.size();
25 536 vec<mint> ans(n);
26 268 vecuu v2(n);
27
20/20
std::vector<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<14l> >, std::allocator<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<14l> > > > tifa_libs::gen_invseq<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<14l> > >(std::vector<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<14l> >, std::allocator<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<14l> > > > const&):
✓ Branch 3 taken 90459540 times.
✓ Branch 4 taken 26 times.
std::vector<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<15l> >, std::allocator<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<15l> > > > tifa_libs::gen_invseq<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<15l> > >(std::vector<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<15l> >, std::allocator<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<15l> > > > const&):
✓ Branch 3 taken 90459540 times.
✓ Branch 4 taken 26 times.
std::vector<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<16l> >, std::allocator<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<16l> > > > tifa_libs::gen_invseq<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<16l> > >(std::vector<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<16l> >, std::allocator<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<16l> > > > const&):
✓ Branch 3 taken 271378620 times.
✓ Branch 4 taken 78 times.
std::vector<tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<70l> >, std::allocator<tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<70l> > > > tifa_libs::gen_invseq<tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<70l> > >(std::vector<tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<70l> >, std::allocator<tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<70l> > > > const&):
✓ Branch 3 taken 1001000 times.
✓ Branch 4 taken 2 times.
std::vector<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<14l> >, std::allocator<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<14l> > > > tifa_libs::gen_invseq<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<14l> > >(std::vector<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<14l> >, std::allocator<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<14l> > > > const&):
✓ Branch 3 taken 90459540 times.
✓ Branch 4 taken 26 times.
std::vector<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<15l> >, std::allocator<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<15l> > > > tifa_libs::gen_invseq<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<15l> > >(std::vector<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<15l> >, std::allocator<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<15l> > > > const&):
✓ Branch 3 taken 90459540 times.
✓ Branch 4 taken 26 times.
std::vector<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<16l> >, std::allocator<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<16l> > > > tifa_libs::gen_invseq<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<16l> > >(std::vector<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<16l> >, std::allocator<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<16l> > > > const&):
✓ Branch 3 taken 271378620 times.
✓ Branch 4 taken 78 times.
std::vector<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<69l> >, std::allocator<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<69l> > > > tifa_libs::gen_invseq<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<69l> > >(std::vector<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<69l> >, std::allocator<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<69l> > > > const&):
✓ Branch 3 taken 1001000 times.
✓ Branch 4 taken 2 times.
std::vector<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> >, std::allocator<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > > tifa_libs::gen_invseq<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > >(std::vector<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> >, std::allocator<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > > const&):
✓ Branch 3 taken 1001000 times.
✓ Branch 4 taken 2 times.
std::vector<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, std::allocator<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > > tifa_libs::gen_invseq<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > >(std::vector<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, std::allocator<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > > const&):
✓ Branch 3 taken 1001000 times.
✓ Branch 4 taken 2 times.
908599668 flt_ (u32, i, 0, n) v2[i] = v[i].val();
28 268 auto _ = gen_invseq(v2, mint::mod());
29
20/20
std::vector<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<14l> >, std::allocator<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<14l> > > > tifa_libs::gen_invseq<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<14l> > >(std::vector<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<14l> >, std::allocator<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<14l> > > > const&):
✓ Branch 3 taken 90459540 times.
✓ Branch 4 taken 26 times.
std::vector<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<15l> >, std::allocator<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<15l> > > > tifa_libs::gen_invseq<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<15l> > >(std::vector<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<15l> >, std::allocator<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<15l> > > > const&):
✓ Branch 3 taken 90459540 times.
✓ Branch 4 taken 26 times.
std::vector<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<16l> >, std::allocator<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<16l> > > > tifa_libs::gen_invseq<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<16l> > >(std::vector<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<16l> >, std::allocator<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<16l> > > > const&):
✓ Branch 3 taken 271378620 times.
✓ Branch 4 taken 78 times.
std::vector<tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<70l> >, std::allocator<tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<70l> > > > tifa_libs::gen_invseq<tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<70l> > >(std::vector<tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<70l> >, std::allocator<tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<70l> > > > const&):
✓ Branch 3 taken 1001000 times.
✓ Branch 4 taken 2 times.
std::vector<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<14l> >, std::allocator<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<14l> > > > tifa_libs::gen_invseq<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<14l> > >(std::vector<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<14l> >, std::allocator<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<14l> > > > const&):
✓ Branch 3 taken 90459540 times.
✓ Branch 4 taken 26 times.
std::vector<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<15l> >, std::allocator<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<15l> > > > tifa_libs::gen_invseq<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<15l> > >(std::vector<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<15l> >, std::allocator<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<15l> > > > const&):
✓ Branch 3 taken 90459540 times.
✓ Branch 4 taken 26 times.
std::vector<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<16l> >, std::allocator<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<16l> > > > tifa_libs::gen_invseq<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<16l> > >(std::vector<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<16l> >, std::allocator<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<16l> > > > const&):
✓ Branch 3 taken 271378620 times.
✓ Branch 4 taken 78 times.
std::vector<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<69l> >, std::allocator<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<69l> > > > tifa_libs::gen_invseq<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<69l> > >(std::vector<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<69l> >, std::allocator<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<69l> > > > const&):
✓ Branch 3 taken 1001000 times.
✓ Branch 4 taken 2 times.
std::vector<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> >, std::allocator<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > > tifa_libs::gen_invseq<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > >(std::vector<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> >, std::allocator<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > > const&):
✓ Branch 3 taken 1001000 times.
✓ Branch 4 taken 2 times.
std::vector<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, std::allocator<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > > tifa_libs::gen_invseq<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > >(std::vector<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, std::allocator<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > > const&):
✓ Branch 3 taken 1001000 times.
✓ Branch 4 taken 2 times.
908599668 flt_ (u32, i, 0, n) ans[i] = _[i];
30 268 return ans;
31 268 }
32
33 } // namespace tifa_libs
34