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> as SemiRing>::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 316)
301pub fn floor_sum_polynomial_i64<T, const X: usize, const Y: usize>(
302 l: i64,
303 r: i64,
304 a: i64,
305 b: i64,
306 m: u64,
307) -> [[T; Y]; X]
308where
309 T: Clone + Zero + One + Add<Output = T> + Mul<Output = T>,
310 <AddMulOperation<T> as SemiRing>::Additive: Invertible,
311{
312 assert!(l <= r);
313 assert!(m > 0);
314
315 if a < 0 {
316 let mut ans = floor_sum_polynomial_i64::<T, X, Y>(-r + 1, -l + 1, -a, b, m);
317 for i in (1..X).step_by(2) {
318 for j in 0..Y {
319 ans[i][j] = AddMulOperation::<T>::neg(&ans[i][j]);
320 }
321 }
322 return ans;
323 }
324
325 let add_x = l;
326 let n = (r - l) as u64;
327 let b = a * add_x + b;
328
329 let add_y = b.div_euclid(m as i64);
330 let b = b.rem_euclid(m as i64);
331 assert!(a >= 0);
332 assert!(b >= 0);
333 let data = floor_monoid_product::<FloorSum<AddMulOperation<T>, X, Y>>(
334 FloorSum::<AddMulOperation<T>, X, Y>::to_x(),
335 FloorSum::<AddMulOperation<T>, X, Y>::to_y(),
336 n,
337 a as u64,
338 b as u64,
339 m,
340 );
341
342 let offset = FloorSum::<AddMulOperation<T>, X, Y>::offset(add_x, add_y);
343 FloorSum::<AddMulOperation<T>, X, Y>::operate(&offset, &data).dp
344}