1use crate::algebra::{
4 AddMulOperation, Associative, DotProduct, Field, Group, Invertible, Magma, Monoid, Ring,
5 SemiRing, Unital,
6};
7use crate::array;
8use crate::data_structure::BitSet;
9#[cfg(target_arch = "x86_64")]
10use crate::num::montgomery_simd;
11use crate::num::{
12 BarrettReduction, Complex, ExtendedGcd, MInt, MIntBase, MIntConvert, MIntDotProduct, One,
13 RangeBoundsExt, Signed, Unsigned, Wrapping, Zero, montgomery,
14};
15use crate::tools::{AssociatedValue, PartialIgnoredOrd, SerdeByteStr, Xorshift, advise_huge_pages};
16#[cfg(target_arch = "x86_64")]
17use crate::tools::{SimdBackend, simd_backend};
18
19#[codesnip::entry("ArbitraryModBinomial")]
20pub use self::arbitrary_mod_binomial::ArbitraryModBinomial;
21#[codesnip::entry("ArrayVec")]
22pub use self::array_vec::{ArrayVec, ToArrayVec, ToArrayVecScalar};
23#[codesnip::entry("BinomialPrefixSum")]
24pub use self::binomial_prefix_sum::{BinomialPolynomialPrefixSum, BinomialPrefixSum};
25#[codesnip::entry("BitMatrix")]
26pub use self::bit_matrix::{BitMatrix, BitMatrixSolution};
27#[codesnip::entry("bitwise_transform")]
28pub use self::bitwise_transform::bitwise_transform;
29#[codesnip::entry("BitwiseandConvolve")]
30pub use self::bitwiseand_convolve::{
31 BitwiseandConvolve, OnlineSupersetMobiusTransform, OnlineSupersetZetaTransform,
32};
33#[codesnip::entry("BitwiseorConvolve")]
34pub use self::bitwiseor_convolve::{
35 BitwiseorConvolve, OnlineSubsetMobiusTransform, OnlineSubsetZetaTransform,
36};
37#[codesnip::entry("BitwisexorConvolve")]
38pub use self::bitwisexor_convolve::BitwisexorConvolve;
39#[codesnip::entry("BlackBoxMatrix")]
40pub use self::black_box_matrix::{BlackBoxMatrix, BlackBoxMatrixImpl, SparseMatrix};
41#[codesnip::entry("BlackBoxMIntMatrix")]
42pub use self::black_box_mint_matrix::BlackBoxMIntMatrix;
43#[codesnip::entry("ConvolveSteps")]
44pub use self::convolve_steps::ConvolveSteps;
45#[codesnip::entry("discrete_logarithm")]
46pub use self::discrete_logarithm::{discrete_logarithm, discrete_logarithm_prime_mod};
47#[codesnip::entry("factorial")]
48pub use self::factorial::MemorizedFactorial;
49#[codesnip::entry("fast_fourier_transform")]
50pub use self::fast_fourier_transform::ConvolveRealFft;
51#[codesnip::entry("FastPrimeMod")]
52pub use self::fast_prime_mod::FastPrimeMod;
53#[codesnip::entry("floor_sum")]
54pub use self::floor_sum::{
55 floor_power_sum, floor_sum, floor_sum_i64, floor_sum_polynomial, floor_sum_polynomial_i64,
56 floor_sum_range_freq, min_of_mod_of_linear,
57};
58#[codesnip::entry("FormalPowerSeries")]
59pub use self::formal_power_series::{
60 FormalPowerSeries, FormalPowerSeriesCoefficient, FormalPowerSeriesCoefficientSqrt, Fps,
61 Fps998244353,
62};
63#[codesnip::entry("garner")]
64pub use self::garner::Garner;
65pub use self::gcd::*;
66#[codesnip::entry("GcdConvolve")]
67pub use self::gcd_convolve::GcdConvolve;
68#[codesnip::entry("lagrange_interpolation")]
69pub use self::lagrange_interpolation::{lagrange_interpolation, lagrange_interpolation_polynomial};
70#[codesnip::entry("LcmConvolve")]
71pub use self::lcm_convolve::LcmConvolve;
72#[codesnip::entry("linear_congruence")]
73pub use self::linear_congruence::{solve_linear_congruence, solve_simultaneous_linear_congruence};
74#[codesnip::entry("linear_diophantine")]
75pub use self::linear_diophantine::solve_linear_diophantine;
76#[codesnip::entry("Matrix")]
77pub use self::matrix::Matrix;
78#[codesnip::entry("miller_rabin")]
79pub use self::miller_rabin::{miller_rabin, miller_rabin_with_br};
80#[codesnip::entry("min_plus_convolution")]
81pub use self::min_plus_convolution::*;
82#[codesnip::entry("MIntMatrix")]
83pub use self::mint_matrix::MIntMatrix;
84#[codesnip::entry("NumberTheoreticTransform")]
85pub use self::number_theoretic_transform::{
86 Convolve, Convolve998244353, MIntConvolve, NttReuse, U64Convolve,
87};
88pub use self::polynomial::*;
89#[codesnip::entry("PowPrec")]
90pub use self::pow_prec::PowPrec;
91pub use self::prime::*;
92#[codesnip::entry("prime_factors")]
93pub use self::prime_factors::{divisors, prime_factors, prime_factors_flatten};
94#[codesnip::entry("PrimeList")]
95pub use self::prime_list::{PrimeList, with_prime_list};
96#[codesnip::entry("PrimeTable")]
97pub use self::prime_table::PrimeTable;
98#[codesnip::entry("primitive_root")]
99pub use self::primitive_root::{check_primitive_root, primitive_root};
100#[codesnip::entry("QuotientArray")]
101pub use self::quotient_array::QuotientArray;
102#[codesnip::entry("RelaxedConvolution")]
103pub use self::relaxed_convolution::RelaxedConvolution;
104#[codesnip::entry("SubsetConvolve")]
105pub use self::subset_convolve::SubsetConvolve;
106
107#[cfg_attr(
108 nightly,
109 codesnip::entry(
110 "ArbitraryModBinomial",
111 include("BarrettReduction", "integer", "linear_congruence", "prime_factors")
112 )
113)]
114mod arbitrary_mod_binomial;
115#[cfg_attr(nightly, codesnip::entry("ArrayVec"))]
116mod array_vec;
117#[cfg_attr(
118 nightly,
119 codesnip::entry("BinomialPrefixSum", include("factorial", "MIntBase", "mo_algorithm"))
120)]
121mod binomial_prefix_sum;
122#[cfg_attr(nightly, codesnip::entry("BitMatrix", include("BitSet", "avx_helper")))]
123mod bit_matrix;
124#[cfg_attr(nightly, codesnip::entry("bitwise_transform"))]
125mod bitwise_transform;
126#[cfg_attr(
127 nightly,
128 codesnip::entry("BitwiseandConvolve", include("_zeta_transform", "bitwise_transform"))
129)]
130mod bitwiseand_convolve;
131#[cfg_attr(
132 nightly,
133 codesnip::entry("BitwiseorConvolve", include("_zeta_transform", "bitwise_transform"))
134)]
135mod bitwiseor_convolve;
136#[cfg_attr(
137 nightly,
138 codesnip::entry("BitwisexorConvolve", include("_zeta_transform", "bitwise_transform"))
139)]
140mod bitwisexor_convolve;
141#[cfg_attr(nightly, codesnip::entry("BlackBoxMatrix", include("Matrix")))]
142mod black_box_matrix;
143#[cfg_attr(
144 nightly,
145 codesnip::entry(
146 "BlackBoxMIntMatrix",
147 include("BlackBoxMatrix", "FormalPowerSeries", "MIntDotProduct", "Xorshift")
148 )
149)]
150mod black_box_mint_matrix;
151#[cfg_attr(nightly, codesnip::entry("ConvolveSteps"))]
152mod convolve_steps;
153#[cfg_attr(
154 nightly,
155 codesnip::entry(
156 "discrete_logarithm",
157 include(
158 "BarrettReduction",
159 "lcm",
160 "modinv",
161 "primitive_root",
162 "PrimeList",
163 "Xorshift"
164 )
165 )
166)]
167mod discrete_logarithm;
168#[cfg_attr(nightly, codesnip::entry("factorial", include("MIntBase")))]
169mod factorial;
170#[cfg_attr(
171 nightly,
172 codesnip::entry(
173 "fast_fourier_transform",
174 include(
175 "Complex",
176 "AssociatedValue",
177 "ConvolveSteps",
178 "avx_helper",
179 "_huge_pages"
180 )
181 )
182)]
183mod fast_fourier_transform;
184#[cfg_attr(
185 nightly,
186 codesnip::entry(
187 "FastPrimeMod",
188 include("BarrettReduction", "miller_rabin", "primitive_root", "Xorshift")
189 )
190)]
191mod fast_prime_mod;
192#[cfg_attr(
193 nightly,
194 codesnip::entry("floor_sum", include("algebra", "ring", "integer", "BarrettReduction"))
195)]
196mod floor_sum;
197#[cfg_attr(
198 nightly,
199 codesnip::entry(
200 "FormalPowerSeries",
201 include(
202 "NumberTheoreticTransform",
203 "montgomery",
204 "mod_sqrt",
205 "factorial",
206 "PartialIgnoredOrd",
207 "gcd"
208 )
209 )
210)]
211mod formal_power_series;
212#[cfg_attr(nightly, codesnip::entry(include("integer")))]
213mod garner;
214mod gcd;
215#[cfg_attr(
216 nightly,
217 codesnip::entry("GcdConvolve", include("_zeta_transform", "PrimeList"))
218)]
219mod gcd_convolve;
220#[cfg_attr(
221 nightly,
222 codesnip::entry("lagrange_interpolation", include("factorial", "MIntBase"))
223)]
224mod lagrange_interpolation;
225#[cfg_attr(
226 nightly,
227 codesnip::entry("LcmConvolve", include("_zeta_transform", "PrimeList"))
228)]
229mod lcm_convolve;
230#[cfg_attr(nightly, codesnip::entry(include("integer")))]
231mod linear_congruence;
232#[cfg_attr(nightly, codesnip::entry(include("integer", "discrete_steps")))]
233mod linear_diophantine;
234#[cfg_attr(nightly, codesnip::entry("Matrix", include("zero_one", "ring")))]
235mod matrix;
236#[cfg_attr(nightly, codesnip::entry("miller_rabin", include("BarrettReduction")))]
237mod miller_rabin;
238#[cfg_attr(
239 nightly,
240 codesnip::entry("min_plus_convolution", include("integer", "NumberTheoreticTransform"))
241)]
242mod min_plus_convolution;
243#[cfg(target_arch = "x86_64")]
244#[cfg_attr(nightly, codesnip::entry("NumberTheoreticTransform"))]
245mod mint_fft_convolve;
246#[cfg_attr(
247 nightly,
248 codesnip::entry(
249 "MIntMatrix",
250 include("Matrix", "MIntDotProduct", "factorial", "Xorshift")
251 )
252)]
253mod mint_matrix;
254#[cfg_attr(nightly, codesnip::entry("mod_sqrt", include("MIntBase")))]
255mod mod_sqrt;
256#[cfg_attr(
257 nightly,
258 codesnip::entry(
259 "NumberTheoreticTransform",
260 include(
261 "MInt",
262 "montgomery",
263 "montgomery_simd",
264 "ConvolveSteps",
265 "avx_helper",
266 "fast_fourier_transform",
267 "_huge_pages"
268 )
269 )
270)]
271mod number_theoretic_transform;
272mod polynomial;
273#[cfg_attr(
274 nightly,
275 codesnip::entry("PowPrec", include("MIntBase", "prime_factors"))
276)]
277mod pow_prec;
278mod prime;
279#[cfg_attr(
280 nightly,
281 codesnip::entry("prime_factors", include("miller_rabin", "gcd", "Xorshift"))
282)]
283mod prime_factors;
284#[cfg_attr(nightly, codesnip::entry("PrimeList"))]
285mod prime_list;
286#[cfg_attr(nightly, codesnip::entry("PrimeTable"))]
287mod prime_table;
288#[cfg_attr(nightly, codesnip::entry("primitive_root", include("prime_factors")))]
289mod primitive_root;
290#[cfg_attr(
291 nightly,
292 codesnip::entry("QuotientArray", include("algebra", "ring", "PrimeList"))
293)]
294mod quotient_array;
295#[cfg_attr(
296 nightly,
297 codesnip::entry("RelaxedConvolution", include("ConvolveSteps", "zero_one"))
298)]
299mod relaxed_convolution;
300#[cfg_attr(
301 nightly,
302 codesnip::entry("SubsetConvolve", include("BitwiseorConvolve", "_huge_pages"))
303)]
304mod subset_convolve;
305
306#[codesnip::entry("_zeta_transform", include("algebra", "ring", "ConvolveSteps"))]
307#[codesnip::skip]
308#[allow(dead_code)]
309#[doc(hidden)]
310enum ZetaTransformSnippets {}
311
312#[codesnip::entry(when("Matrix", "coding"))]
313impl<R> SerdeByteStr for Matrix<R>
314where
315 R: SemiRing<T: SerdeByteStr>,
316{
317 fn serialize(&self, buf: &mut Vec<u8>) {
318 self.data.serialize(buf);
319 }
320
321 fn deserialize<I>(iter: &mut I) -> Self
322 where
323 I: Iterator<Item = u8>,
324 {
325 Self::from_vec(Vec::deserialize(iter))
326 }
327}