src/fps/compinv/lib.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include "../../comb/seq/inv/lib.hpp" | ||
| 4 | #include "../exp/lib.hpp" | ||
| 5 | #include "../ln/lib.hpp" | ||
| 6 | #include "../powem/lib.hpp" | ||
| 7 | #include "../shl/lib.hpp" | ||
| 8 | |||
| 9 | namespace tifa_libs { | ||
| 10 | |||
| 11 | // @return g s.t. $g(f(x)) \equiv x \pmod{\deg(f)+1}$ | ||
| 12 | template <poly_c poly_t, class T> | ||
| 13 | 153 | CEXP auto compinv_fps(poly_t CR f, vec<T> CR inv, u32 n = 0) NE { | |
| 14 |
12/24auto tifa_libs::compinv_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > >, unsigned long>(tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > > const&, std::vector<unsigned long, std::allocator<unsigned long> > const&, unsigned int):
✓ Branch 1 taken 51 times.
✗ Branch 2 not taken.
✓ Branch 6 taken 51 times.
✗ Branch 7 not taken.
✓ Branch 11 taken 51 times.
✗ Branch 12 not taken.
✓ Branch 14 taken 51 times.
✗ Branch 15 not taken.
auto tifa_libs::compinv_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > >, unsigned long>(tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > > const&, std::vector<unsigned long, std::allocator<unsigned long> > const&, unsigned int):
✓ Branch 1 taken 51 times.
✗ Branch 2 not taken.
✓ Branch 6 taken 51 times.
✗ Branch 7 not taken.
✓ Branch 11 taken 51 times.
✗ Branch 12 not taken.
✓ Branch 14 taken 51 times.
✗ Branch 15 not taken.
auto tifa_libs::compinv_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > >, unsigned long>(tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > > const&, std::vector<unsigned long, std::allocator<unsigned long> > const&, unsigned int):
✓ Branch 1 taken 51 times.
✗ Branch 2 not taken.
✓ Branch 6 taken 51 times.
✗ Branch 7 not taken.
✓ Branch 11 taken 51 times.
✗ Branch 12 not taken.
✓ Branch 14 taken 51 times.
✗ Branch 15 not taken.
|
153 | if (assert(f.size() > 1 && f[0] == 0 && f[1] != 0); !n) n = (u32)f.size(); |
| 15 |
3/6auto tifa_libs::compinv_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > >, unsigned long>(tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > > const&, std::vector<unsigned long, std::allocator<unsigned long> > const&, unsigned int):
✗ Branch 0 not taken.
✓ Branch 1 taken 51 times.
auto tifa_libs::compinv_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > >, unsigned long>(tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > > const&, std::vector<unsigned long, std::allocator<unsigned long> > const&, unsigned int):
✗ Branch 0 not taken.
✓ Branch 1 taken 51 times.
auto tifa_libs::compinv_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > >, unsigned long>(tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > > const&, std::vector<unsigned long, std::allocator<unsigned long> > const&, unsigned int):
✗ Branch 0 not taken.
✓ Branch 1 taken 51 times.
|
153 | if (n < 2) return poly_t{0, f[1].inv()}.pre(n); |
| 16 | 153 | poly_t h = powem_fps(f) * (n - 1); | |
| 17 |
6/6auto tifa_libs::compinv_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > >, unsigned long>(tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > > const&, std::vector<unsigned long, std::allocator<unsigned long> > const&, unsigned int):
✓ Branch 4 taken 1182732 times.
✓ Branch 5 taken 51 times.
auto tifa_libs::compinv_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > >, unsigned long>(tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > > const&, std::vector<unsigned long, std::allocator<unsigned long> > const&, unsigned int):
✓ Branch 4 taken 1182732 times.
✓ Branch 5 taken 51 times.
auto tifa_libs::compinv_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > >, unsigned long>(tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > > const&, std::vector<unsigned long, std::allocator<unsigned long> > const&, unsigned int):
✓ Branch 4 taken 1182732 times.
✓ Branch 5 taken 51 times.
|
3548349 | flt_ (u32, k, 1, n) h[k] *= inv[k]; |
| 18 | 153 | h.reverse(), h *= h[0].inv(); | |
| 19 | 153 | poly_t g = exp_fps(ln_fps(h) * (-TPN poly_t::val_t{n - 1}).inv()); | |
| 20 | 153 | g *= f[1].inv(); | |
| 21 | 153 | return shl_fps(g, 1).pre(n); | |
| 22 | 153 | } | |
| 23 | // @return g s.t. $g(f(x)) \equiv x \pmod{\deg(f)+1}$ | ||
| 24 | template <poly_c poly_t> | ||
| 25 | 153 | CEXP auto compinv_fps(poly_t CR f, u32 n = 0) NE { return compinv_fps(f, gen_inv((u32)f.size(), poly_t::val_t::mod()), n); } | |
| 26 | |||
| 27 | } // namespace tifa_libs | ||
| 28 |