src/conv/add/u128/lib.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include "../../../math/ds/mint/ms/lib.hpp" | ||
| 4 | #include "../../trans/ntt/lib.hpp" | ||
| 5 | #include "../dft/lib.hpp" | ||
| 6 | #include "../naive/lib.hpp" | ||
| 7 | |||
| 8 | namespace tifa_libs { | ||
| 9 | |||
| 10 | // max = 167772161 * 469762049 * 754974721 \approx 5.95e25 | ||
| 11 | template <class T> | ||
| 12 | 30280 | vec<u128> conv_u128(vec<T> CR l, vec<T> CR r, u32 ans_size = 0) NE { | |
| 13 |
1/2✓ Branch 0 taken 30280 times.
✗ Branch 1 not taken.
|
30280 | if (!ans_size) ans_size = u32(l.size() + r.size() - 1); |
| 14 |
1/2✗ Branch 3 not taken.
✓ Branch 4 taken 30280 times.
|
30280 | if (min(l.size(), r.size()) < CONV_NAIVE_THRESHOLD) return conv_naive<T, u128>(l, r, ans_size); |
| 15 | static CEXP u32 m0 = 167772161, m1 = 469762049, m2 = 754974721; | ||
| 16 | using mint0 = mint_ms<m0>; | ||
| 17 | using mint1 = mint_ms<m1>; | ||
| 18 | using mint2 = mint_ms<m2>; | ||
| 19 | static CEXP u32 r01 = inverse(m0, mint1::mod()), | ||
| 20 | r02 = inverse(m0, mint2::mod()), | ||
| 21 | r12 = inverse(m1, mint2::mod()), | ||
| 22 | r02r12 = (u64)r02 * r12 % m2; | ||
| 23 | static CEXP u64 w1 = m0, w2 = (u64)m0 * m1; | ||
| 24 |
3/4✓ Branch 0 taken 56 times.
✓ Branch 1 taken 30224 times.
✓ Branch 3 taken 56 times.
✗ Branch 4 not taken.
|
30280 | static ntt<mint0> ntt0; |
| 25 |
3/4✓ Branch 0 taken 56 times.
✓ Branch 1 taken 30224 times.
✓ Branch 3 taken 56 times.
✗ Branch 4 not taken.
|
30280 | static ntt<mint1> ntt1; |
| 26 |
3/4✓ Branch 0 taken 56 times.
✓ Branch 1 taken 30224 times.
✓ Branch 3 taken 56 times.
✗ Branch 4 not taken.
|
30280 | static ntt<mint2> ntt2; |
| 27 | 30280 | cvec<mint0> d0 = conv_dft_um<ntt<mint0>, mint0>(ntt0, l, r, ans_size); | |
| 28 | 30280 | cvec<mint1> d1 = conv_dft_um<ntt<mint1>, mint1>(ntt1, l, r, ans_size); | |
| 29 | 30280 | cvec<mint2> d2 = conv_dft_um<ntt<mint2>, mint2>(ntt2, l, r, ans_size); | |
| 30 | 30280 | vec<u128> ret(ans_size); | |
| 31 |
2/2✓ Branch 0 taken 42583578 times.
✓ Branch 1 taken 30280 times.
|
42613858 | flt_ (u32, i, 0, ans_size) { |
| 32 | 42583578 | cu64 n1 = d1[i].val(), n2 = d2[i].val(), | |
| 33 | 42583578 | a = d0[i].val(), b = (n1 + m1 - a) * r01 % m1; | |
| 34 | 42583578 | cu128 c = ((n2 + m2 - a) * r02r12 + (m2 - b) * r12) % m2; | |
| 35 | 42583578 | ret[i] = a + b * w1 + c * w2; | |
| 36 | } | ||
| 37 | 30280 | return ret; | |
| 38 | 30280 | } | |
| 39 | |||
| 40 | } // namespace tifa_libs | ||
| 41 |