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

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

	Coverage	Exec / Excl / Total
Lines:	100.0%	48 / 0 / 48
Functions:	100.0%	3 / 0 / 3
Branches:	92.9%	39 / 0 / 42

Line	Branch	Exec	Source
1			#pragma once
2
3			#include "../divmod/lib.hpp"
4
5			namespace tifa_libs {
6
7			// @return b s.t. $f(x) = \sum_{i=0}^{n-1} b_i \prod_{j=0}^{i-1}(x - p_j)$
8			template <poly_c poly_t>
9		45	CEXP auto cbm2n_fps(poly_t CR f, vec<typename poly_t::val_t> CR p) NE {
10		45	cu32 n = (u32)p.size();
11	3/6 auto tifa_libs::cbm2n_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > > >(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<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > >::val_t, std::allocator<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > >::val_t> > const&): ✗ Branch 1 not taken. ✓ Branch 2 taken 15 times. auto tifa_libs::cbm2n_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > > >(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<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > >::val_t, std::allocator<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > >::val_t> > const&): ✗ Branch 1 not taken. ✓ Branch 2 taken 15 times. auto tifa_libs::cbm2n_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > > >(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<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > >::val_t, std::allocator<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > >::val_t> > const&): ✗ Branch 1 not taken. ✓ Branch 2 taken 15 times.	45	assert(f.size() == n);
12		45	cu32 m = std::bit_ceil(n);
13		45	vec<poly_t> s(2 * m, poly_t{0, 1});
14	6/6 auto tifa_libs::cbm2n_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > > >(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<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > >::val_t, std::allocator<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > >::val_t> > const&): ✓ Branch 0 taken 1130508 times. ✓ Branch 1 taken 15 times. auto tifa_libs::cbm2n_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > > >(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<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > >::val_t, std::allocator<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > >::val_t> > const&): ✓ Branch 0 taken 1130508 times. ✓ Branch 1 taken 15 times. auto tifa_libs::cbm2n_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > > >(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<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > >::val_t, std::allocator<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > >::val_t> > const&): ✓ Branch 0 taken 1130508 times. ✓ Branch 1 taken 15 times.	3391569	flt_ (u32, i, 0, m)
15	6/6 auto tifa_libs::cbm2n_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > > >(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<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > >::val_t, std::allocator<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > >::val_t> > const&): ✓ Branch 0 taken 927185 times. ✓ Branch 1 taken 203323 times. auto tifa_libs::cbm2n_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > > >(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<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > >::val_t, std::allocator<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > >::val_t> > const&): ✓ Branch 0 taken 927185 times. ✓ Branch 1 taken 203323 times. auto tifa_libs::cbm2n_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > > >(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<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > >::val_t, std::allocator<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > >::val_t> > const&): ✓ Branch 0 taken 927185 times. ✓ Branch 1 taken 203323 times.	3391524	if (i < n) s[m + i][0] = -p[i];
16	6/6 auto tifa_libs::cbm2n_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > > >(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<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > >::val_t, std::allocator<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > >::val_t> > const&): ✓ Branch 0 taken 1130493 times. ✓ Branch 1 taken 15 times. auto tifa_libs::cbm2n_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > > >(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<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > >::val_t, std::allocator<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > >::val_t> > const&): ✓ Branch 0 taken 1130493 times. ✓ Branch 1 taken 15 times. auto tifa_libs::cbm2n_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > > >(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<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > >::val_t, std::allocator<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > >::val_t> > const&): ✓ Branch 0 taken 1130493 times. ✓ Branch 1 taken 15 times.	3391524	for (u32 i = m - 1; i; --i) {
17	6/6 auto tifa_libs::cbm2n_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > > >(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<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > >::val_t, std::allocator<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > >::val_t> > const&): ✓ Branch 1 taken 185 times. ✓ Branch 2 taken 1130308 times. auto tifa_libs::cbm2n_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > > >(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<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > >::val_t, std::allocator<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > >::val_t> > const&): ✓ Branch 1 taken 185 times. ✓ Branch 2 taken 1130308 times. auto tifa_libs::cbm2n_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > > >(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<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > >::val_t, std::allocator<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > >::val_t> > const&): ✓ Branch 1 taken 185 times. ✓ Branch 2 taken 1130308 times.	3391479	if (std::has_single_bit(i + 1)) continue;
18		3390924	s[i] = s[2 * i] * s[2 * i + 1];
19			}
20		45	s[1] = f;
21	6/6 auto tifa_libs::cbm2n_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > > >(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<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > >::val_t, std::allocator<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > >::val_t> > const&): ✓ Branch 8 taken 1130493 times. ✓ Branch 9 taken 15 times. auto tifa_libs::cbm2n_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > > >(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<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > >::val_t, std::allocator<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > >::val_t> > const&): ✓ Branch 8 taken 1130493 times. ✓ Branch 9 taken 15 times. auto tifa_libs::cbm2n_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > > >(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<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > >::val_t, std::allocator<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > >::val_t> > const&): ✓ Branch 8 taken 1130493 times. ✓ Branch 9 taken 15 times.	3391524	flt_ (u32, i, 1, m) std::tie(s[2 * i + 1], s[2 * i]) = divmod_fps(s[i], s[2 * i]);
22		45	poly_t b(n);
23	6/6 auto tifa_libs::cbm2n_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > > >(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<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > >::val_t, std::allocator<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > >::val_t> > const&): ✓ Branch 3 taken 927185 times. ✓ Branch 4 taken 15 times. auto tifa_libs::cbm2n_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > > >(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<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > >::val_t, std::allocator<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > >::val_t> > const&): ✓ Branch 3 taken 927185 times. ✓ Branch 4 taken 15 times. auto tifa_libs::cbm2n_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > > >(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<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > >::val_t, std::allocator<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > >::val_t> > const&): ✓ Branch 3 taken 927185 times. ✓ Branch 4 taken 15 times.	2781600	flt_ (u32, i, 0, n) b[i] = s[m + i][0];
24		45	return b;
25		45	}
26
27			} // namespace tifa_libs
28

1

#pragma once

2

3

#include "../divmod/lib.hpp"

4

5

namespace tifa_libs {

6

7

// @return b s.t. $f(x) = \sum_{i=0}^{n-1} b_i \prod_{j=0}^{i-1}(x - p_j)$

8

template <poly_c poly_t>

9

45

CEXP auto cbm2n_fps(poly_t CR f, vec<typename poly_t::val_t> CR p) NE {

10

45

cu32 n = (u32)p.size();

11

3/6

auto tifa_libs::cbm2n_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > > >(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<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > >::val_t, std::allocator<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > >::val_t> > const&):

✗ Branch 1 not taken.

✓ Branch 2 taken 15 times.

auto tifa_libs::cbm2n_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > > >(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<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > >::val_t, std::allocator<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > >::val_t> > const&):

✗ Branch 1 not taken.

✓ Branch 2 taken 15 times.

auto tifa_libs::cbm2n_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > > >(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<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > >::val_t, std::allocator<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > >::val_t> > const&):

✗ Branch 1 not taken.

✓ Branch 2 taken 15 times.

45

assert(f.size() == n);

12

45

cu32 m = std::bit_ceil(n);

13

45

vec<poly_t> s(2 * m, poly_t{0, 1});

14

6/6

auto tifa_libs::cbm2n_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > > >(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<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > >::val_t, std::allocator<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > >::val_t> > const&):

✓ Branch 0 taken 1130508 times.

✓ Branch 1 taken 15 times.

auto tifa_libs::cbm2n_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > > >(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<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > >::val_t, std::allocator<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > >::val_t> > const&):

✓ Branch 0 taken 1130508 times.

✓ Branch 1 taken 15 times.

auto tifa_libs::cbm2n_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > > >(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<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > >::val_t, std::allocator<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > >::val_t> > const&):

✓ Branch 0 taken 1130508 times.

✓ Branch 1 taken 15 times.

3391569

flt_ (u32, i, 0, m)

15

6/6

auto tifa_libs::cbm2n_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > > >(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<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > >::val_t, std::allocator<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > >::val_t> > const&):

✓ Branch 0 taken 927185 times.

✓ Branch 1 taken 203323 times.

auto tifa_libs::cbm2n_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > > >(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<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > >::val_t, std::allocator<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > >::val_t> > const&):

✓ Branch 0 taken 927185 times.

✓ Branch 1 taken 203323 times.

auto tifa_libs::cbm2n_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > > >(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<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > >::val_t, std::allocator<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > >::val_t> > const&):

✓ Branch 0 taken 927185 times.

✓ Branch 1 taken 203323 times.

3391524

if (i < n) s[m + i][0] = -p[i];

16

6/6

auto tifa_libs::cbm2n_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > > >(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<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > >::val_t, std::allocator<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > >::val_t> > const&):

✓ Branch 0 taken 1130493 times.

✓ Branch 1 taken 15 times.

auto tifa_libs::cbm2n_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > > >(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<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > >::val_t, std::allocator<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > >::val_t> > const&):

✓ Branch 0 taken 1130493 times.

✓ Branch 1 taken 15 times.

auto tifa_libs::cbm2n_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > > >(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<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > >::val_t, std::allocator<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > >::val_t> > const&):

✓ Branch 0 taken 1130493 times.

✓ Branch 1 taken 15 times.

3391524

for (u32 i = m - 1; i; --i) {

17

6/6

auto tifa_libs::cbm2n_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > > >(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<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > >::val_t, std::allocator<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > >::val_t> > const&):

✓ Branch 1 taken 185 times.

✓ Branch 2 taken 1130308 times.

auto tifa_libs::cbm2n_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > > >(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<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > >::val_t, std::allocator<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > >::val_t> > const&):

✓ Branch 1 taken 185 times.

✓ Branch 2 taken 1130308 times.

auto tifa_libs::cbm2n_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > > >(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<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > >::val_t, std::allocator<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > >::val_t> > const&):

✓ Branch 1 taken 185 times.

✓ Branch 2 taken 1130308 times.

3391479

if (std::has_single_bit(i + 1)) continue;

18

3390924

s[i] = s[2 * i] * s[2 * i + 1];

19

}

20

45

s[1] = f;

21

6/6

auto tifa_libs::cbm2n_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > > >(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<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > >::val_t, std::allocator<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > >::val_t> > const&):

✓ Branch 8 taken 1130493 times.

✓ Branch 9 taken 15 times.

auto tifa_libs::cbm2n_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > > >(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<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > >::val_t, std::allocator<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > >::val_t> > const&):

✓ Branch 8 taken 1130493 times.

✓ Branch 9 taken 15 times.

auto tifa_libs::cbm2n_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > > >(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<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > >::val_t, std::allocator<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > >::val_t> > const&):

✓ Branch 8 taken 1130493 times.

✓ Branch 9 taken 15 times.

3391524

flt_ (u32, i, 1, m) std::tie(s[2 * i + 1], s[2 * i]) = divmod_fps(s[i], s[2 * i]);

22

45

poly_t b(n);

23

6/6

auto tifa_libs::cbm2n_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > > >(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<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > >::val_t, std::allocator<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > >::val_t> > const&):

✓ Branch 3 taken 927185 times.

✓ Branch 4 taken 15 times.

auto tifa_libs::cbm2n_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > > >(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<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > >::val_t, std::allocator<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > >::val_t> > const&):

✓ Branch 3 taken 927185 times.

✓ Branch 4 taken 15 times.

auto tifa_libs::cbm2n_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > > >(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<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > >::val_t, std::allocator<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > >::val_t> > const&):

✓ Branch 3 taken 927185 times.

✓ Branch 4 taken 15 times.

2781600

flt_ (u32, i, 0, n) b[i] = s[m + i][0];

24

45

return b;

25

45

}

26

27

} // namespace tifa_libs

28