GCC Code Coverage Report

Directory: ./
Coverage: low: ≥ 0% medium: ≥ 75.0% high: ≥ 90.0%
Coverage Exec / Excl / Total
Lines: 100.0% 21 / 0 / 21
Functions: 100.0% 3 / 0 / 3
Branches: 66.7% 12 / 0 / 18
src/math/lrec/nth_term/lib.hpp
Line Branch Exec Source
1 #pragma once
2
3 #include "../../../fps/bostan_mori/lib.hpp"
4 #include "../berlekamp_massey/lib.hpp"
5
6 namespace tifa_libs {
7
8 template <class poly, std::same_as<TPN poly::val_t> mint>
9 60 CEXP mint nth_term_lrec(u64 n, vec<mint> CR a, vec<mint> CR bm) NE {
10
6/6
tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > tifa_libs::nth_term_lrec<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > >, tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > >(unsigned long, std::vector<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> >, std::allocator<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > > const&, std::vector<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> >, std::allocator<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > > const&):
✓ Branch 1 taken 5 times.
✓ Branch 2 taken 15 times.
tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > tifa_libs::nth_term_lrec<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > >, tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > >(unsigned long, 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&, 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 1 taken 5 times.
✓ Branch 2 taken 15 times.
tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > tifa_libs::nth_term_lrec<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > >, tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > >(unsigned long, 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&, 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 1 taken 5 times.
✓ Branch 2 taken 15 times.
 60 if (n < a.size()) return a[n];
11
6/12
tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > tifa_libs::nth_term_lrec<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > >, tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > >(unsigned long, std::vector<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> >, std::allocator<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > > const&, std::vector<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> >, std::allocator<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > > const&):
✓ Branch 1 taken 15 times.
✗ Branch 2 not taken.
✓ Branch 6 taken 15 times.
✗ Branch 7 not taken.
tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > tifa_libs::nth_term_lrec<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > >, tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > >(unsigned long, 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&, 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 1 taken 15 times.
✗ Branch 2 not taken.
✓ Branch 6 taken 15 times.
✗ Branch 7 not taken.
tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > tifa_libs::nth_term_lrec<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > >, tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > >(unsigned long, 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&, 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 1 taken 15 times.
✗ Branch 2 not taken.
✓ Branch 6 taken 15 times.
✗ Branch 7 not taken.
 45 assert(!bm.empty() && bm[0] == 1);
12 45 poly q(bm);
13 45 q.strip();
14 45 return bostan_mori(n, (poly(a) * q).pre((u32)q.size() - 1), q);
15 45 }
16 template <class poly, std::same_as<TPN poly::val_t> mint>
17 CEXP mint nth_term_lrec(u64 n, vec<mint> CR a) NE {
18 if (n < a.size()) return a[n];
19 auto bm = berlekamp_massey(a);
20 return nth_term_lrec<poly, mint>(n, a, bm);
21 }
22
23 } // namespace tifa_libs
24