fn calc<M, C>(
a: &[usize],
b: &[usize],
f: &[MInt<M>],
g: &[MInt<M>],
) -> Vec<MInt<M>>Examples found in repository?
crates/competitive/src/algorithm/number_of_increasing_sequences_between.rs (line 39)
6pub fn number_of_increasing_sequences_between<M, C>(a: &[usize], b: &[usize]) -> MInt<M>
7where
8 M: MIntBase,
9 C: ConvolveSteps<T = Vec<MInt<M>>>,
10{
11 let n = a.len();
12 assert_eq!(n, b.len());
13 if n == 0 {
14 return MInt::<M>::one();
15 }
16 let mut a = a.to_vec();
17 let mut b = b.to_vec();
18 for i in 1..n {
19 if a[i - 1] > a[i] {
20 a[i] = a[i - 1];
21 }
22 }
23 for i in (1..n).rev() {
24 if b[i - 1] > b[i] {
25 b[i - 1] = b[i];
26 }
27 }
28 if a.iter().zip(b.iter()).any(|(&l, &r)| l >= r) {
29 return MInt::<M>::zero();
30 }
31 let len = n + b[n - 1];
32 let mut l = vec![0usize; len];
33 let mut r = vec![!0usize; len];
34 l[len - 1] = b[n - 1] - 1;
35 for (i, (&a, &b)) in a.iter().zip(b.iter()).enumerate() {
36 l[i + a] = a;
37 r[i + b] = b;
38 }
39 calc::<M, C>(&l, &r, &[MInt::one()], &[MInt::one(), MInt::one()])
40 .iter()
41 .fold(MInt::zero(), |s, &x| s + x)
42}