GCC Code Coverage Report

Directory: ./
Coverage: low: ≥ 0% medium: ≥ 75.0% high: ≥ 90.0%
Coverage Exec / Excl / Total
Lines: 100.0% 89 / 0 / 89
Functions: 100.0% 11 / 0 / 11
Branches: 98.4% 61 / 0 / 62
src/math/interp/lagrange0/lib.hpp
Line Branch Exec Source
1 #pragma once
2
3 #include "../../../comb/seq/ifact/lib.hpp"
4 #include "../../mul_mod/lib.hpp"
5
6 namespace tifa_libs {
7
8 299 CEXP i64 lagrange_interp0(spnii v, u64 x, u64 mod, spnuu ifact) NE {
9 299 cu32 n = (u32)v.size();
10
3/4
✗ Branch 0 not taken.
✓ Branch 1 taken 299 times.
✓ Branch 3 taken 23 times.
✓ Branch 4 taken 276 times.
 299 retif_((assert(n); n == 1) [[unlikely]], v[0]);
11
2/2
✓ Branch 0 taken 92 times.
✓ Branch 1 taken 184 times.
 276 if (x < n) return v[x];
12 184 vecuu pre(n);
13
2/2
✓ Branch 1 taken 920230345 times.
✓ Branch 2 taken 184 times.
 920230529 flt_ (u32, i, 0, n) pre[i] = x - i;
14
2/2
✓ Branch 4 taken 920230161 times.
✓ Branch 5 taken 184 times.
 920230345 flt_ (u32, i, 1, n) pre[i] = mul_mod_u(pre[i], pre[i - 1], mod);
15 184 vecuu suc(n);
16
2/2
✓ Branch 1 taken 920230345 times.
✓ Branch 2 taken 184 times.
 920230529 flt_ (u32, i, 0, n) suc[i] = x - i;
17
2/2
✓ Branch 4 taken 920230161 times.
✓ Branch 5 taken 184 times.
 920230345 for (u32 i = n - 2; ~i; --i) suc[i] = mul_mod_u(suc[i], suc[i + 1], mod);
18 184 i64 ans = 0;
19
2/2
✓ Branch 0 taken 920230345 times.
✓ Branch 1 taken 184 times.
 920230529 flt_ (u32, i, 0, n) {
20 920230345 i64 _ = v[i];
21
2/2
✓ Branch 0 taken 920230161 times.
✓ Branch 1 taken 184 times.
 920230345 if (i) _ = mul_mod_s(_, (i64)pre[i - 1], mod);
22
2/2
✓ Branch 0 taken 920230161 times.
✓ Branch 1 taken 184 times.
 920230345 if (i + 1 < n) _ = mul_mod_s(_, (i64)suc[i + 1], mod);
23 920230345 _ = mul_mod_s(mul_mod_s(_, (i64)ifact[i], mod), (i64)ifact[n - i - 1], mod);
24
2/2
✓ Branch 0 taken 460115138 times.
✓ Branch 1 taken 460115207 times.
 920230345 ans = (ans + ((n - i) % 2 ? _ : (i64)mod - _)) % (i64)mod;
25 }
26 184 return ans;
27 184 }
28 CEXP i64 lagrange_interp0(spnii v, u64 x, u64 mod) NE { return lagrange_interp0(v, x, mod, gen_ifact((u32)v.size(), mod)); }
29 template <class mint>
30 299 CEXP mint lagrange_interp0(vec<mint> CR v, u64 x, vec<mint> CR ifact) NE {
31 299 vecii _(v.size());
32
20/20
tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<13l> > tifa_libs::lagrange_interp0<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<13l> > >(std::vector<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<13l> >, std::allocator<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<13l> > > > const&, unsigned long, std::vector<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<13l> >, std::allocator<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<13l> > > > const&):
✓ Branch 4 taken 60020022 times.
✓ Branch 5 taken 13 times.
tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<14l> > tifa_libs::lagrange_interp0<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&, unsigned long, 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 4 taken 60020022 times.
✓ Branch 5 taken 13 times.
tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<15l> > tifa_libs::lagrange_interp0<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&, unsigned long, 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 4 taken 180060066 times.
✓ Branch 5 taken 39 times.
tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > tifa_libs::lagrange_interp0<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > >(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&, 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&):
✓ Branch 4 taken 360120132 times.
✓ Branch 5 taken 78 times.
tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<13l> > tifa_libs::lagrange_interp0<tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<13l> > >(std::vector<tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<13l> >, std::allocator<tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<13l> > > > const&, unsigned long, std::vector<tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<13l> >, std::allocator<tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<13l> > > > const&):
✓ Branch 4 taken 60020022 times.
✓ Branch 5 taken 13 times.
tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<15l> > tifa_libs::lagrange_interp0<tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<15l> > >(std::vector<tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<15l> >, std::allocator<tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<15l> > > > const&, unsigned long, std::vector<tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<15l> >, std::allocator<tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<15l> > > > const&):
✓ Branch 4 taken 60020022 times.
✓ Branch 5 taken 13 times.
tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<13l> > tifa_libs::lagrange_interp0<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<13l> > >(std::vector<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<13l> >, std::allocator<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<13l> > > > const&, unsigned long, std::vector<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<13l> >, std::allocator<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<13l> > > > const&):
✓ Branch 4 taken 60020022 times.
✓ Branch 5 taken 13 times.
tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<15l> > tifa_libs::lagrange_interp0<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&, unsigned long, 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 4 taken 60020022 times.
✓ Branch 5 taken 13 times.
tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > tifa_libs::lagrange_interp0<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&, 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&):
✓ Branch 4 taken 120040044 times.
✓ Branch 5 taken 26 times.
tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > tifa_libs::lagrange_interp0<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&, 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&):
✓ Branch 4 taken 360120132 times.
✓ Branch 5 taken 78 times.
 1380460805 flt_ (u32, i, 0, (u32)v.size()) _[i] = (i64)v[i].val();
33 299 vecuu ifa(ifact.size());
34
20/20
tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<13l> > tifa_libs::lagrange_interp0<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<13l> > >(std::vector<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<13l> >, std::allocator<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<13l> > > > const&, unsigned long, std::vector<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<13l> >, std::allocator<tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<13l> > > > const&):
✓ Branch 4 taken 60020042 times.
✓ Branch 5 taken 13 times.
tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<14l> > tifa_libs::lagrange_interp0<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&, unsigned long, 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 4 taken 74000023 times.
✓ Branch 5 taken 13 times.
tifa_libs::mint_impl_::mint<tifa_libs::mint_bd_tag<15l> > tifa_libs::lagrange_interp0<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&, unsigned long, 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 4 taken 222000069 times.
✓ Branch 5 taken 39 times.
tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > tifa_libs::lagrange_interp0<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > >(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&, 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&):
✓ Branch 4 taken 430020157 times.
✓ Branch 5 taken 78 times.
tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<13l> > tifa_libs::lagrange_interp0<tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<13l> > >(std::vector<tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<13l> >, std::allocator<tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<13l> > > > const&, unsigned long, std::vector<tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<13l> >, std::allocator<tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<13l> > > > const&):
✓ Branch 4 taken 60020042 times.
✓ Branch 5 taken 13 times.
tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<15l> > tifa_libs::lagrange_interp0<tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<15l> > >(std::vector<tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<15l> >, std::allocator<tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<15l> > > > const&, unsigned long, std::vector<tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<15l> >, std::allocator<tifa_libs::mint_impl_::mint<tifa_libs::mint_md64_tag<15l> > > > const&):
✓ Branch 4 taken 74000023 times.
✓ Branch 5 taken 13 times.
tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<13l> > tifa_libs::lagrange_interp0<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<13l> > >(std::vector<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<13l> >, std::allocator<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<13l> > > > const&, unsigned long, std::vector<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<13l> >, std::allocator<tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<13l> > > > const&):
✓ Branch 4 taken 60020042 times.
✓ Branch 5 taken 13 times.
tifa_libs::mint_impl_::mint<tifa_libs::mint_md_tag<15l> > tifa_libs::lagrange_interp0<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&, unsigned long, 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 4 taken 74000023 times.
✓ Branch 5 taken 13 times.
tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > tifa_libs::lagrange_interp0<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&, 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&):
✓ Branch 4 taken 134020065 times.
✓ Branch 5 taken 26 times.
tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > tifa_libs::lagrange_interp0<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&, 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&):
✓ Branch 4 taken 430020157 times.
✓ Branch 5 taken 78 times.
 1618120942 flt_ (u32, i, 0, (u32)ifact.size()) ifa[i] = ifact[i].val();
35 299 return mint(lagrange_interp0(_, x, mint::mod(), ifa));
36 299 }
37 template <class mint>
38 CEXP mint lagrange_interp0(vec<mint> CR v, u64 x) NE { return lagrange_interp0(v, x, mint::mod(), gen_ifact<mint>(v.size())); }
39
40 } // namespace tifa_libs
41