pub fn floor_sum_polynomial_i64<T, const X: usize, const Y: usize>(
l: i64,
r: i64,
a: i64,
b: i64,
m: u64,
) -> [[T; Y]; X]where
T: Clone + Zero + One + Add<Output = T> + Mul<Output = T>,
AddMulOperation<T>: SemiRing<T = T, Additive: Invertible>,Expand description
$$\sum_{i=l}^{r-1}i^X\left\lfloor\frac{a\times i+b}{m}\right\rfloor^Y$$
Examples found in repository?
crates/competitive/src/math/floor_sum.rs (line 315)
300pub fn floor_sum_polynomial_i64<T, const X: usize, const Y: usize>(
301 l: i64,
302 r: i64,
303 a: i64,
304 b: i64,
305 m: u64,
306) -> [[T; Y]; X]
307where
308 T: Clone + Zero + One + Add<Output = T> + Mul<Output = T>,
309 AddMulOperation<T>: SemiRing<T = T, Additive: Invertible>,
310{
311 assert!(l <= r);
312 assert!(m > 0);
313
314 if a < 0 {
315 let mut ans = floor_sum_polynomial_i64::<T, X, Y>(-r + 1, -l + 1, -a, b, m);
316 for ans in ans.iter_mut().skip(1).step_by(2) {
317 for ans in ans.iter_mut() {
318 *ans = AddMulOperation::<T>::neg(ans);
319 }
320 }
321 return ans;
322 }
323
324 let add_x = l;
325 let n = (r - l) as u64;
326 let b = a * add_x + b;
327
328 let add_y = b.div_euclid(m as i64);
329 let b = b.rem_euclid(m as i64);
330 assert!(a >= 0);
331 assert!(b >= 0);
332 let data = floor_monoid_product::<FloorSum<AddMulOperation<T>, X, Y>>(
333 FloorSum::<AddMulOperation<T>, X, Y>::to_x(),
334 FloorSum::<AddMulOperation<T>, X, Y>::to_y(),
335 n,
336 a as u64,
337 b as u64,
338 m,
339 );
340
341 let offset = FloorSum::<AddMulOperation<T>, X, Y>::offset(add_x, add_y);
342 FloorSum::<AddMulOperation<T>, X, Y>::operate(&offset, &data).dp
343}