fn finite_extrema<T>(values: &[T]) -> Option<(T, T)>where
T: Signed,Examples found in repository?
crates/competitive/src/math/min_plus_convolution/mod.rs (line 206)
197pub fn min_plus_convolution_bounded_ntt<T>(a: &[T], b: &[T]) -> Vec<T>
198where
199 T: Signed + TryFrom<usize>,
200 T::Unsigned: TryInto<usize>,
201{
202 let output_len = output_len(a.len(), b.len());
203 if output_len == 0 {
204 return Vec::new();
205 }
206 let (Some(a_extrema), Some(b_extrema)) = (finite_extrema(a), finite_extrema(b)) else {
207 return vec![T::maximum(); output_len];
208 };
209 let requirements = bounded_requirements_from_extrema(a.len(), b.len(), a_extrema, b_extrema)
210 .expect("bounded min-plus convolution encoding must fit the 2^23 NTT limit");
211 let mut left = vec![MInt998244353::from(0_u32); a.len() * requirements.base];
212 let mut right = vec![MInt998244353::from(0_u32); b.len() * requirements.base];
213 for (index, &value) in a.iter().enumerate() {
214 if !value.is_maximum() {
215 let normalized: usize = value
216 .abs_diff(requirements.a_min)
217 .try_into()
218 .ok()
219 .expect("bounded min-plus convolution value span must fit usize");
220 left[index * requirements.base + normalized] = MInt998244353::from(1_u32);
221 }
222 }
223 for (index, &value) in b.iter().enumerate() {
224 if !value.is_maximum() {
225 let normalized: usize = value
226 .abs_diff(requirements.b_min)
227 .try_into()
228 .ok()
229 .expect("bounded min-plus convolution value span must fit usize");
230 right[index * requirements.base + normalized] = MInt998244353::from(1_u32);
231 }
232 }
233 let coefficients = Convolve998244353::convolve(left, right);
234 let encoded_len = output_len
235 .checked_mul(requirements.base)
236 .expect("bounded min-plus convolution encoded length must fit usize");
237 let mut result = Vec::with_capacity(output_len);
238 for chunk in coefficients[..encoded_len].chunks_exact(requirements.base) {
239 let value = if let Some(normalized) = chunk.iter().position(|&value| u32::from(value) != 0)
240 {
241 requirements.a_min
242 + requirements.b_min
243 + T::try_from(normalized)
244 .ok()
245 .expect("bounded min-plus convolution value must fit the output type")
246 } else {
247 T::maximum()
248 };
249 result.push(value);
250 }
251 result
252}