competitive/math/
mod.rs

1//! mathematical datas
2
3use crate::algebra::{
4    AddMulOperation, Associative, Field, Group, Invertible, Magma, Monoid, Ring, SemiRing, Unital,
5};
6use crate::array;
7use crate::num::{
8    BarrettReduction, Complex, ExtendedGcd, MInt, MIntBase, MIntConvert, One, RangeBoundsExt,
9    Signed, Unsigned, Wrapping, Zero, montgomery,
10};
11use crate::tools::{AssociatedValue, PartialIgnoredOrd, SerdeByteStr, Xorshift};
12#[cfg(target_arch = "x86_64")]
13use crate::tools::{SimdBackend, simd_backend};
14
15#[codesnip::entry("ArbitraryModBinomial")]
16pub use self::arbitrary_mod_binomial::ArbitraryModBinomial;
17#[codesnip::entry("ArrayVec")]
18pub use self::array_vec::{ArrayVec, ToArrayVec, ToArrayVecScalar};
19#[codesnip::entry("berlekamp_massey")]
20pub use self::berlekamp_massey::berlekamp_massey;
21#[codesnip::entry("bitwise_transform")]
22pub use self::bitwise_transform::bitwise_transform;
23#[codesnip::entry("BitwiseandConvolve")]
24pub use self::bitwiseand_convolve::{
25    BitwiseandConvolve, OnlineSupersetMobiusTransform, OnlineSupersetZetaTransform,
26};
27#[codesnip::entry("BitwiseorConvolve")]
28pub use self::bitwiseor_convolve::{
29    BitwiseorConvolve, OnlineSubsetMobiusTransform, OnlineSubsetZetaTransform,
30};
31#[codesnip::entry("BitwisexorConvolve")]
32pub use self::bitwisexor_convolve::BitwisexorConvolve;
33#[codesnip::entry("BlackBoxMatrix")]
34pub use self::black_box_matrix::{
35    BlackBoxMIntMatrix, BlackBoxMatrix, BlackBoxMatrixImpl, SparseMatrix,
36};
37#[codesnip::entry("ConvolveSteps")]
38pub use self::convolve_steps::ConvolveSteps;
39#[codesnip::entry("discrete_logarithm")]
40pub use self::discrete_logarithm::{discrete_logarithm, discrete_logarithm_prime_mod};
41#[codesnip::entry("factorial")]
42pub use self::factorial::MemorizedFactorial;
43#[codesnip::entry("fast_fourier_transform")]
44pub use self::fast_fourier_transform::ConvolveRealFft;
45#[codesnip::entry("floor_sum")]
46pub use self::floor_sum::{
47    floor_power_sum, floor_sum, floor_sum_i64, floor_sum_polynomial, floor_sum_polynomial_i64,
48    floor_sum_range_freq,
49};
50#[codesnip::entry("FormalPowerSeries")]
51pub use self::formal_power_series::{
52    FormalPowerSeries, FormalPowerSeriesCoefficient, FormalPowerSeriesCoefficientSqrt, Fps,
53    Fps998244353,
54};
55#[codesnip::entry("garner")]
56pub use self::garner::Garner;
57pub use self::gcd::*;
58#[codesnip::entry("GcdConvolve")]
59pub use self::gcd_convolve::GcdConvolve;
60#[codesnip::entry("lagrange_interpolation")]
61pub use self::lagrange_interpolation::{lagrange_interpolation, lagrange_interpolation_polynomial};
62#[codesnip::entry("LcmConvolve")]
63pub use self::lcm_convolve::LcmConvolve;
64#[codesnip::entry("linear_congruence")]
65pub use self::linear_congruence::{solve_linear_congruence, solve_simultaneous_linear_congruence};
66#[codesnip::entry("linear_diophantine")]
67pub use self::linear_diophantine::solve_linear_diophantine;
68#[codesnip::entry("Matrix")]
69pub use self::matrix::Matrix;
70#[codesnip::entry("miller_rabin")]
71pub use self::miller_rabin::{miller_rabin, miller_rabin_with_br};
72#[codesnip::entry("MIntMatrix")]
73pub use self::mint_matrix::MIntMatrix;
74#[codesnip::entry("NumberTheoreticTransform")]
75pub use self::number_theoretic_transform::{
76    Convolve, Convolve998244353, MIntConvolve, NttReuse, U64Convolve,
77};
78pub use self::polynomial::*;
79#[codesnip::entry("PowPrec")]
80pub use self::pow_prec::PowPrec;
81pub use self::prime::*;
82#[codesnip::entry("prime_factors")]
83pub use self::prime_factors::{divisors, prime_factors, prime_factors_flatten};
84#[codesnip::entry("PrimeList")]
85pub use self::prime_list::{PrimeList, with_prime_list};
86#[codesnip::entry("PrimeTable")]
87pub use self::prime_table::PrimeTable;
88#[codesnip::entry("primitive_root")]
89pub use self::primitive_root::{check_primitive_root, primitive_root};
90#[codesnip::entry("QuotientArray")]
91pub use self::quotient_array::QuotientArray;
92#[codesnip::entry("RelaxedConvolution")]
93pub use self::relaxed_convolution::RelaxedConvolution;
94#[codesnip::entry("SubsetConvolve")]
95pub use self::subset_convolve::SubsetConvolve;
96
97#[cfg_attr(
98    nightly,
99    codesnip::entry(
100        "ArbitraryModBinomial",
101        include("BarrettReduction", "integer", "linear_congruence", "prime_factors")
102    )
103)]
104mod arbitrary_mod_binomial;
105#[cfg_attr(nightly, codesnip::entry("ArrayVec"))]
106mod array_vec;
107#[cfg_attr(nightly, codesnip::entry("berlekamp_massey", include("zero_one")))]
108mod berlekamp_massey;
109#[cfg_attr(nightly, codesnip::entry("bitwise_transform"))]
110mod bitwise_transform;
111#[cfg_attr(
112    nightly,
113    codesnip::entry("BitwiseandConvolve", include("_zeta_transform", "bitwise_transform"))
114)]
115mod bitwiseand_convolve;
116#[cfg_attr(
117    nightly,
118    codesnip::entry("BitwiseorConvolve", include("_zeta_transform", "bitwise_transform"))
119)]
120mod bitwiseor_convolve;
121#[cfg_attr(
122    nightly,
123    codesnip::entry("BitwisexorConvolve", include("_zeta_transform", "bitwise_transform"))
124)]
125mod bitwisexor_convolve;
126#[cfg_attr(
127    nightly,
128    codesnip::entry("BlackBoxMatrix", include("FormalPowerSeries", "Matrix", "Xorshift"))
129)]
130mod black_box_matrix;
131#[cfg_attr(nightly, codesnip::entry("ConvolveSteps"))]
132mod convolve_steps;
133#[cfg_attr(
134    nightly,
135    codesnip::entry(
136        "discrete_logarithm",
137        include(
138            "BarrettReduction",
139            "lcm",
140            "modinv",
141            "primitive_root",
142            "PrimeList",
143            "Xorshift"
144        )
145    )
146)]
147mod discrete_logarithm;
148#[cfg_attr(nightly, codesnip::entry("factorial", include("MIntBase")))]
149mod factorial;
150#[cfg_attr(
151    nightly,
152    codesnip::entry(
153        "fast_fourier_transform",
154        include("Complex", "AssociatedValue", "ConvolveSteps")
155    )
156)]
157mod fast_fourier_transform;
158#[cfg_attr(
159    nightly,
160    codesnip::entry("floor_sum", include("algebra", "ring", "integer", "BarrettReduction"))
161)]
162mod floor_sum;
163#[cfg_attr(
164    nightly,
165    codesnip::entry(
166        "FormalPowerSeries",
167        include(
168            "NumberTheoreticTransform",
169            "montgomery",
170            "mod_sqrt",
171            "factorial",
172            "PartialIgnoredOrd",
173            "berlekamp_massey"
174        )
175    )
176)]
177mod formal_power_series;
178#[cfg_attr(nightly, codesnip::entry(include("integer")))]
179mod garner;
180mod gcd;
181#[cfg_attr(
182    nightly,
183    codesnip::entry("GcdConvolve", include("_zeta_transform", "PrimeList"))
184)]
185mod gcd_convolve;
186#[cfg_attr(
187    nightly,
188    codesnip::entry("lagrange_interpolation", include("factorial", "MIntBase"))
189)]
190mod lagrange_interpolation;
191#[cfg_attr(
192    nightly,
193    codesnip::entry("LcmConvolve", include("_zeta_transform", "PrimeList"))
194)]
195mod lcm_convolve;
196#[cfg_attr(nightly, codesnip::entry(include("integer")))]
197mod linear_congruence;
198#[cfg_attr(nightly, codesnip::entry(include("integer", "discrete_steps")))]
199mod linear_diophantine;
200#[cfg_attr(
201    nightly,
202    codesnip::entry("Matrix", include("zero_one", "ring", "coding"))
203)]
204mod matrix;
205#[cfg_attr(nightly, codesnip::entry("miller_rabin", include("BarrettReduction")))]
206mod miller_rabin;
207#[cfg_attr(
208    nightly,
209    codesnip::entry("MIntMatrix", include("Matrix", "factorial", "Xorshift"))
210)]
211mod mint_matrix;
212#[cfg_attr(nightly, codesnip::entry("mod_sqrt", include("MIntBase")))]
213mod mod_sqrt;
214#[cfg_attr(
215    nightly,
216    codesnip::entry(
217        "NumberTheoreticTransform",
218        include("montgomery", "ConvolveSteps", "avx_helper")
219    )
220)]
221mod number_theoretic_transform;
222mod polynomial;
223#[cfg_attr(
224    nightly,
225    codesnip::entry("PowPrec", include("MIntBase", "prime_factors"))
226)]
227mod pow_prec;
228mod prime;
229#[cfg_attr(
230    nightly,
231    codesnip::entry("prime_factors", include("miller_rabin", "gcd"))
232)]
233mod prime_factors;
234#[cfg_attr(nightly, codesnip::entry("PrimeList"))]
235mod prime_list;
236#[cfg_attr(nightly, codesnip::entry("PrimeTable"))]
237mod prime_table;
238#[cfg_attr(nightly, codesnip::entry("primitive_root", include("prime_factors")))]
239mod primitive_root;
240#[cfg_attr(
241    nightly,
242    codesnip::entry("QuotientArray", include("algebra", "ring", "PrimeList"))
243)]
244mod quotient_array;
245#[cfg_attr(
246    nightly,
247    codesnip::entry("RelaxedConvolution", include("ConvolveSteps", "zero_one"))
248)]
249mod relaxed_convolution;
250#[cfg_attr(
251    nightly,
252    codesnip::entry("SubsetConvolve", include("BitwiseorConvolve"))
253)]
254mod subset_convolve;
255
256#[codesnip::entry("_zeta_transform", include("algebra", "ring", "ConvolveSteps"))]
257#[codesnip::skip]
258#[allow(dead_code)]
259#[doc(hidden)]
260enum ZetaTransformSnippets {}
competitive/math/mod.rs

competitive/math/
mod.rs
