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/20std::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/20std::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 |