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

competitive/math/
mod.rs
