src/fps/bostan_mori/lib.hpp - GCC Code Coverage Report

Directory:	./
Coverage:	low: ≥ 0% medium: ≥ 75.0% high: ≥ 90.0%

	Coverage	Exec / Excl / Total
Lines:	100.0%	99 / 0 / 99
Functions:	100.0%	6 / 0 / 6
Branches:	87.5%	42 / 0 / 48

    src/fps/bostan_mori/lib.hpp
    
        Line
        Branch
        Exec
        Source
      
        #pragma once
      
        #include "../../conv/trans/ntt_doubling/lib.hpp"
      
        #include "../ds/poly_c/lib.hpp"
      
        namespace tifa_libs {
      
        namespace bostan_mori_impl_ {
      
        template <class ccore_t, class T>
      
        1803
        vec<T> coeff_(ccore_t CR core, ccore_t CR core2, vec<T>& q, u64 n, u32 d) NE {
      
        1803
          cu32 len = core.size();
      
        1803
          vec<T> s(len * 2);
      
          6/6std::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> > > > tifa_libs::bostan_mori_impl_::coeff_<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> > >(tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > const&, tifa_libs::polyntt_impl_::cconv_ntt<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> > > >&, unsigned long, unsigned int):
✓ Branch 0 taken 15 times.
✓ Branch 1 taken 586 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::bostan_mori_impl_::coeff_<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> > >(tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > const&, tifa_libs::polyntt_impl_::cconv_ntt<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> > > >&, unsigned long, unsigned int):
✓ Branch 0 taken 15 times.
✓ Branch 1 taken 586 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::bostan_mori_impl_::coeff_<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> > >(tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > const&, tifa_libs::polyntt_impl_::cconv_ntt<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> > > >&, unsigned long, unsigned int):
✓ Branch 0 taken 15 times.
✓ Branch 1 taken 586 times.

        1803
          if (!n) {
      
        45
            vec<T> res(d);
      
        45
            res.back() = len * std::reduce(q.begin(), q.begin() + len, T(0)).inv();
      
        45
            return res;
      
        45
          }
      
        1758
          ntt_doubling(core, q, len);
      
        1758
          vec<T> a(len * 2);
      
          6/6std::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> > > > tifa_libs::bostan_mori_impl_::coeff_<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> > >(tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > const&, tifa_libs::polyntt_impl_::cconv_ntt<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> > > >&, unsigned long, unsigned int):
✓ Branch 5 taken 28385478 times.
✓ Branch 6 taken 586 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::bostan_mori_impl_::coeff_<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> > >(tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > const&, tifa_libs::polyntt_impl_::cconv_ntt<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> > > >&, unsigned long, unsigned int):
✓ Branch 5 taken 28385478 times.
✓ Branch 6 taken 586 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::bostan_mori_impl_::coeff_<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> > >(tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > const&, tifa_libs::polyntt_impl_::cconv_ntt<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> > > >&, unsigned long, unsigned int):
✓ Branch 5 taken 28385478 times.
✓ Branch 6 taken 586 times.

        85158192
          flt_ (u32, i, len / 2, len) a[i * 2 + 1] = a[i * 2] = q[i * 2] * q[i * 2 + 1];
      
          6/6std::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> > > > tifa_libs::bostan_mori_impl_::coeff_<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> > >(tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > const&, tifa_libs::polyntt_impl_::cconv_ntt<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> > > >&, unsigned long, unsigned int):
✓ Branch 4 taken 56770956 times.
✓ Branch 5 taken 586 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::bostan_mori_impl_::coeff_<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> > >(tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > const&, tifa_libs::polyntt_impl_::cconv_ntt<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> > > >&, unsigned long, unsigned int):
✓ Branch 4 taken 56770956 times.
✓ Branch 5 taken 586 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::bostan_mori_impl_::coeff_<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> > >(tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > const&, tifa_libs::polyntt_impl_::cconv_ntt<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> > > >&, unsigned long, unsigned int):
✓ Branch 4 taken 56770956 times.
✓ Branch 5 taken 586 times.

        170314626
          flt_ (u32, i, 0, len) a[i] = q[i * 2] * q[i * 2 + 1];
      
        1758
          vec<T> w = coeff_(core, core2, a, n / 2, d);
      
        1758
          s = vec<T>(len * 2);
      
          6/6std::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> > > > tifa_libs::bostan_mori_impl_::coeff_<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> > >(tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > const&, tifa_libs::polyntt_impl_::cconv_ntt<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> > > >&, unsigned long, unsigned int):
✓ Branch 2 taken 38123710 times.
✓ Branch 3 taken 586 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::bostan_mori_impl_::coeff_<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> > >(tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > const&, tifa_libs::polyntt_impl_::cconv_ntt<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> > > >&, unsigned long, unsigned int):
✓ Branch 2 taken 38123710 times.
✓ Branch 3 taken 586 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::bostan_mori_impl_::coeff_<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> > >(tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > const&, tifa_libs::polyntt_impl_::cconv_ntt<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> > > >&, unsigned long, unsigned int):
✓ Branch 2 taken 38123710 times.
✓ Branch 3 taken 586 times.

        114372888
          for (u32 i = (n & 1) ^ 1, j = 0; j < d; ++j, i += 2) s[i] = w[j];
      
        1758
          core2.dif(s);
      
          6/6std::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> > > > tifa_libs::bostan_mori_impl_::coeff_<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> > >(tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > const&, tifa_libs::polyntt_impl_::cconv_ntt<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> > > >&, unsigned long, unsigned int):
✓ Branch 3 taken 113541912 times.
✓ Branch 4 taken 586 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::bostan_mori_impl_::coeff_<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> > >(tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > const&, tifa_libs::polyntt_impl_::cconv_ntt<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> > > >&, unsigned long, unsigned int):
✓ Branch 3 taken 113541912 times.
✓ Branch 4 taken 586 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::bostan_mori_impl_::coeff_<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> > >(tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > const&, tifa_libs::polyntt_impl_::cconv_ntt<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> > > >&, unsigned long, unsigned int):
✓ Branch 3 taken 113541912 times.
✓ Branch 4 taken 586 times.

        340627494
          flt_ (u32, i, 0, len * 2) s[i] *= q[i ^ 1];
      
        1758
          core2.dit(s);
      
        1758
          return vec<T>(begin(s) + d, begin(s) + d * 2);
      
        1803
        }
      
        }  // namespace bostan_mori_impl_
      
        // @return [x^k]p/q
      
        template <poly_c poly_t>
      
        45
        CEXP auto bostan_mori(u64 n, poly_t CR p, poly_t CR q) NE {
      
          6/12auto tifa_libs::bostan_mori<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&, tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > > const&):
✓ Branch 2 taken 15 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 15 times.
✗ Branch 6 not taken.
auto tifa_libs::bostan_mori<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&, tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > > const&):
✓ Branch 2 taken 15 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 15 times.
✗ Branch 6 not taken.
auto tifa_libs::bostan_mori<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&, tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > > const&):
✓ Branch 2 taken 15 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 15 times.
✗ Branch 6 not taken.

        45
          if CEXP (assert(p.size() == q.size() - 1 && !p.is_zero()); poly_t::ccore_t::ct_cat != CCORE::NTT) {
      
            auto p_ = p, q_ = q;
      
            while (n) {
      
              auto _ = q_;
      
              for (u32 i = 1; i < _.size(); i += 2) _[i] = -_[i];
      
              auto s = p_ * _, t = q_ * _;
      
              for (u32 i = n & 1; i < s.size(); i += 2) p_[i / 2] = s[i];
      
              for (u32 i = 0; i < t.size(); i += 2) q_[i / 2] = t[i];
      
              n /= 2;
      
            }
      
            return p_[0];
      
          } else {
      
        45
            auto& core = poly_t::conv_core;
      
        45
            auto core2 = core;
      
        45
            cu32 m = (u32)q.size();
      
        45
            core.bzr(m), core2.bzr(core.size() * 2);
      
        45
            auto q_ = q;
      
        45
            core.dif(q_), q_.resize(core2.size());
      
        45
            auto iq = bostan_mori_impl_::coeff_(core, core2, q_, n, m - 1);
      
        45
            TPN poly_t::val_t res = 0;
      
          6/6auto tifa_libs::bostan_mori<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&, tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > > const&):
✓ Branch 6 taken 638591 times.
✓ Branch 7 taken 15 times.
auto tifa_libs::bostan_mori<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&, tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > > const&):
✓ Branch 6 taken 638591 times.
✓ Branch 7 taken 15 times.
auto tifa_libs::bostan_mori<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&, tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > > const&):
✓ Branch 6 taken 638591 times.
✓ Branch 7 taken 15 times.

        1915818
            flt_ (u32, i, 0, iq.size()) res += p[i] * iq[iq.size() - 1 - i];
      
        90
            return res;
      
        45
          }
      
        }
      
        }  // namespace tifa_libs

Line	Branch	Exec	Source
1			#pragma once
2
3			#include "../../conv/trans/ntt_doubling/lib.hpp"
4			#include "../ds/poly_c/lib.hpp"
5
6			namespace tifa_libs {
7			namespace bostan_mori_impl_ {
8			template <class ccore_t, class T>
9		1803	vec<T> coeff_(ccore_t CR core, ccore_t CR core2, vec<T>& q, u64 n, u32 d) NE {
10		1803	cu32 len = core.size();
11		1803	vec<T> s(len * 2);
12	6/6 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> > > > tifa_libs::bostan_mori_impl_::coeff_<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> > >(tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > const&, tifa_libs::polyntt_impl_::cconv_ntt<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> > > >&, unsigned long, unsigned int): ✓ Branch 0 taken 15 times. ✓ Branch 1 taken 586 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::bostan_mori_impl_::coeff_<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> > >(tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > const&, tifa_libs::polyntt_impl_::cconv_ntt<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> > > >&, unsigned long, unsigned int): ✓ Branch 0 taken 15 times. ✓ Branch 1 taken 586 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::bostan_mori_impl_::coeff_<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> > >(tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > const&, tifa_libs::polyntt_impl_::cconv_ntt<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> > > >&, unsigned long, unsigned int): ✓ Branch 0 taken 15 times. ✓ Branch 1 taken 586 times.	1803	if (!n) {
13		45	vec<T> res(d);
14		45	res.back() = len * std::reduce(q.begin(), q.begin() + len, T(0)).inv();
15		45	return res;
16		45	}
17		1758	ntt_doubling(core, q, len);
18		1758	vec<T> a(len * 2);
19	6/6 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> > > > tifa_libs::bostan_mori_impl_::coeff_<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> > >(tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > const&, tifa_libs::polyntt_impl_::cconv_ntt<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> > > >&, unsigned long, unsigned int): ✓ Branch 5 taken 28385478 times. ✓ Branch 6 taken 586 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::bostan_mori_impl_::coeff_<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> > >(tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > const&, tifa_libs::polyntt_impl_::cconv_ntt<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> > > >&, unsigned long, unsigned int): ✓ Branch 5 taken 28385478 times. ✓ Branch 6 taken 586 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::bostan_mori_impl_::coeff_<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> > >(tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > const&, tifa_libs::polyntt_impl_::cconv_ntt<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> > > >&, unsigned long, unsigned int): ✓ Branch 5 taken 28385478 times. ✓ Branch 6 taken 586 times.	85158192	flt_ (u32, i, len / 2, len) a[i * 2 + 1] = a[i * 2] = q[i * 2] * q[i * 2 + 1];
20	6/6 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> > > > tifa_libs::bostan_mori_impl_::coeff_<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> > >(tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > const&, tifa_libs::polyntt_impl_::cconv_ntt<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> > > >&, unsigned long, unsigned int): ✓ Branch 4 taken 56770956 times. ✓ Branch 5 taken 586 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::bostan_mori_impl_::coeff_<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> > >(tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > const&, tifa_libs::polyntt_impl_::cconv_ntt<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> > > >&, unsigned long, unsigned int): ✓ Branch 4 taken 56770956 times. ✓ Branch 5 taken 586 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::bostan_mori_impl_::coeff_<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> > >(tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > const&, tifa_libs::polyntt_impl_::cconv_ntt<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> > > >&, unsigned long, unsigned int): ✓ Branch 4 taken 56770956 times. ✓ Branch 5 taken 586 times.	170314626	flt_ (u32, i, 0, len) a[i] = q[i * 2] * q[i * 2 + 1];
21		1758	vec<T> w = coeff_(core, core2, a, n / 2, d);
22		1758	s = vec<T>(len * 2);
23	6/6 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> > > > tifa_libs::bostan_mori_impl_::coeff_<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> > >(tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > const&, tifa_libs::polyntt_impl_::cconv_ntt<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> > > >&, unsigned long, unsigned int): ✓ Branch 2 taken 38123710 times. ✓ Branch 3 taken 586 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::bostan_mori_impl_::coeff_<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> > >(tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > const&, tifa_libs::polyntt_impl_::cconv_ntt<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> > > >&, unsigned long, unsigned int): ✓ Branch 2 taken 38123710 times. ✓ Branch 3 taken 586 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::bostan_mori_impl_::coeff_<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> > >(tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > const&, tifa_libs::polyntt_impl_::cconv_ntt<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> > > >&, unsigned long, unsigned int): ✓ Branch 2 taken 38123710 times. ✓ Branch 3 taken 586 times.	114372888	for (u32 i = (n & 1) ^ 1, j = 0; j < d; ++j, i += 2) s[i] = w[j];
24		1758	core2.dif(s);
25	6/6 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> > > > tifa_libs::bostan_mori_impl_::coeff_<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> > >(tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > const&, tifa_libs::polyntt_impl_::cconv_ntt<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> > > >&, unsigned long, unsigned int): ✓ Branch 3 taken 113541912 times. ✓ Branch 4 taken 586 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::bostan_mori_impl_::coeff_<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> > >(tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > const&, tifa_libs::polyntt_impl_::cconv_ntt<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> > > >&, unsigned long, unsigned int): ✓ Branch 3 taken 113541912 times. ✓ Branch 4 taken 586 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::bostan_mori_impl_::coeff_<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> > >(tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > const&, tifa_libs::polyntt_impl_::cconv_ntt<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> > > >&, unsigned long, unsigned int): ✓ Branch 3 taken 113541912 times. ✓ Branch 4 taken 586 times.	340627494	flt_ (u32, i, 0, len * 2) s[i] *= q[i ^ 1];
26		1758	core2.dit(s);
27		1758	return vec<T>(begin(s) + d, begin(s) + d * 2);
28		1803	}
29			} // namespace bostan_mori_impl_
30
31			// @return [x^k]p/q
32			template <poly_c poly_t>
33		45	CEXP auto bostan_mori(u64 n, poly_t CR p, poly_t CR q) NE {
34	6/12 auto tifa_libs::bostan_mori<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&, tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > > const&): ✓ Branch 2 taken 15 times. ✗ Branch 3 not taken. ✓ Branch 5 taken 15 times. ✗ Branch 6 not taken. auto tifa_libs::bostan_mori<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&, tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > > const&): ✓ Branch 2 taken 15 times. ✗ Branch 3 not taken. ✓ Branch 5 taken 15 times. ✗ Branch 6 not taken. auto tifa_libs::bostan_mori<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&, tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > > const&): ✓ Branch 2 taken 15 times. ✗ Branch 3 not taken. ✓ Branch 5 taken 15 times. ✗ Branch 6 not taken.	45	if CEXP (assert(p.size() == q.size() - 1 && !p.is_zero()); poly_t::ccore_t::ct_cat != CCORE::NTT) {
35			auto p_ = p, q_ = q;
36			while (n) {
37			auto _ = q_;
38			for (u32 i = 1; i < _.size(); i += 2) _[i] = -_[i];
39			auto s = p_ * _, t = q_ * _;
40			for (u32 i = n & 1; i < s.size(); i += 2) p_[i / 2] = s[i];
41			for (u32 i = 0; i < t.size(); i += 2) q_[i / 2] = t[i];
42			n /= 2;
43			}
44			return p_[0];
45			} else {
46		45	auto& core = poly_t::conv_core;
47		45	auto core2 = core;
48		45	cu32 m = (u32)q.size();
49		45	core.bzr(m), core2.bzr(core.size() * 2);
50		45	auto q_ = q;
51		45	core.dif(q_), q_.resize(core2.size());
52		45	auto iq = bostan_mori_impl_::coeff_(core, core2, q_, n, m - 1);
53		45	TPN poly_t::val_t res = 0;
54	6/6 auto tifa_libs::bostan_mori<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&, tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > > const&): ✓ Branch 6 taken 638591 times. ✓ Branch 7 taken 15 times. auto tifa_libs::bostan_mori<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&, tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > > const&): ✓ Branch 6 taken 638591 times. ✓ Branch 7 taken 15 times. auto tifa_libs::bostan_mori<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&, tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > > const&): ✓ Branch 6 taken 638591 times. ✓ Branch 7 taken 15 times.	1915818	flt_ (u32, i, 0, iq.size()) res += p[i] * iq[iq.size() - 1 - i];
55		90	return res;
56		45	}
57			}
58
59			} // namespace tifa_libs
60