Skip to main content

Shifted

competitive::algorithm::number_of_increasing_sequences_between

Struct Shifted 

Source 
struct Shifted<M>
where
    M: MIntBase,
{
    offset: usize,
    data: Vec<MInt<M>>,
}

Fields§

§offset: usize§data: Vec<MInt<M>>

Implementations§

Source§

impl<M> Shifted<M>
where M: MIntBase,

Source

fn new(offset: usize, data: Vec<MInt<M>>) -> Self

Examples found in repository?
crates/competitive/src/algorithm/number_of_increasing_sequences_between.rs (line 100)
88    fn add(&self, other: &Self) -> Self {
89        let offset = self.offset.min(other.offset);
90        let tail = (self.offset + self.data.len()).max(other.offset + other.data.len());
91        let mut res = vec![MInt::<M>::zero(); tail - offset];
92        let self_start = self.offset - offset;
93        for (i, &v) in self.data.iter().enumerate() {
94            res[self_start + i] += v;
95        }
96        let other_start = other.offset - offset;
97        for (i, &v) in other.data.iter().enumerate() {
98            res[other_start + i] += v;
99        }
100        Self::new(offset, res)
101    }
102
103    fn mul<C>(&self, other: &Self) -> Self
104    where
105        C: ConvolveSteps<T = Vec<MInt<M>>>,
106    {
107        let c = C::convolve(self.data.clone(), other.data.clone());
108        Self::new(self.offset + other.offset, c)
109    }
110
111    fn truncate(&self, l: usize, r: usize) -> Self {
112        let mut offset = self.offset;
113        let mut data = self.data.clone();
114        if offset < l {
115            let drop = l - offset;
116            if drop >= data.len() {
117                data.clear();
118                return Self::new(l, data);
119            }
120            data.drain(..drop);
121            offset = l;
122        }
123        if offset < r {
124            let len = r - offset;
125            if data.len() > len {
126                data.truncate(len);
127            }
128        } else {
129            data.clear();
130        }
131        Self::new(offset, data)
132    }
133
134    fn step<C>(
135        self,
136        s: usize,
137        k: usize,
138        a: &[usize],
139        b: &[usize],
140        pow: &[Self],
141        g_len: usize,
142    ) -> Self
143    where
144        C: ConvolveSteps<T = Vec<MInt<M>>>,
145    {
146        if self.data.is_empty() {
147            return self;
148        }
149        if k == 0 {
150            let res = self.mul::<C>(&pow[0]);
151            return res.truncate(a[s + 1], b[s + 1]);
152        }
153        let len = 1usize << k;
154        let t = s + len;
155        let mut l = a[t];
156        let mut r = b[t];
157        if l < self.offset {
158            l = self.offset;
159        }
160        let max_r = self.offset + self.data.len();
161        let shift = (g_len - 1) << k;
162        r = r.saturating_sub(shift).min(max_r);
163        if l < r {
164            let mut res = Shifted::default();
165            if l > 0 {
166                let f = self.truncate(0, l);
167                let f = f.step::<C>(s, k - 1, a, b, pow, g_len);
168                res = f.step::<C>(s + (1usize << (k - 1)), k - 1, a, b, pow, g_len);
169            }
170            let f = self.truncate(l, r);
171            let g = f.mul::<C>(&pow[k]);
172            res = res.add(&g);
173            if r < max_r {
174                let f = self.truncate(r, !0usize);
175                let f = f.step::<C>(s, k - 1, a, b, pow, g_len);
176                let tail = f.step::<C>(s + (1usize << (k - 1)), k - 1, a, b, pow, g_len);
177                res = res.add(&tail);
178            }
179            res
180        } else {
181            let next = self.step::<C>(s, k - 1, a, b, pow, g_len);
182            next.step::<C>(s + (1usize << (k - 1)), k - 1, a, b, pow, g_len)
183        }
184    }
185}
186
187fn calc<M, C>(a: &[usize], b: &[usize], f: &[MInt<M>], g: &[MInt<M>]) -> Vec<MInt<M>>
188where
189    M: MIntBase,
190    C: ConvolveSteps<T = Vec<MInt<M>>>,
191{
192    if g.is_empty() {
193        return vec![];
194    }
195    let g_len = g.len();
196    let mut a = a.to_vec();
197    let mut b = b.to_vec();
198    let n = a.len();
199    for i in 1..n {
200        if a[i] < a[i - 1] {
201            a[i] = a[i - 1];
202        }
203        let limit = b[i - 1].saturating_add(g_len - 1);
204        if b[i] > limit {
205            b[i] = limit;
206        }
207    }
208    for i in (1..n).rev() {
209        let limit = a[i].saturating_sub(g_len - 1);
210        if a[i - 1] < limit {
211            a[i - 1] = limit;
212        }
213        if b[i - 1] > b[i] {
214            b[i - 1] = b[i];
215        }
216    }
217    if a.iter().zip(b.iter()).any(|(&l, &r)| l >= r) {
218        return vec![];
219    }
220    let k = a.len().next_power_of_two().trailing_zeros() as usize;
221    let mut pow: Vec<Shifted<M>> = Vec::with_capacity(k + 1);
222    pow.push(Shifted::new(0, g.to_vec()));
223    for i in 1..k {
224        let prev = pow[i - 1].clone();
225        pow.push(prev.mul::<C>(&prev));
226    }
227    let mut pos = 0usize;
228    let mut state = Shifted::new(0, f.to_vec());
229    state = state.truncate(a[0], b[0]);
230    for i in (0..k).rev() {
231        let step_len = 1usize << i;
232        if pos + step_len < a.len() {
233            state = state.step::<C>(pos, i, &a, &b, &pow, g_len);
234            pos += step_len;
235        }
236    }
237    let mut res = vec![MInt::<M>::zero(); state.offset];
238    res.extend_from_slice(&state.data);
239    res
240}
Source

fn add(&self, other: &Self) -> Self

Examples found in repository?
crates/competitive/src/algorithm/number_of_increasing_sequences_between.rs (line 172)
134    fn step<C>(
135        self,
136        s: usize,
137        k: usize,
138        a: &[usize],
139        b: &[usize],
140        pow: &[Self],
141        g_len: usize,
142    ) -> Self
143    where
144        C: ConvolveSteps<T = Vec<MInt<M>>>,
145    {
146        if self.data.is_empty() {
147            return self;
148        }
149        if k == 0 {
150            let res = self.mul::<C>(&pow[0]);
151            return res.truncate(a[s + 1], b[s + 1]);
152        }
153        let len = 1usize << k;
154        let t = s + len;
155        let mut l = a[t];
156        let mut r = b[t];
157        if l < self.offset {
158            l = self.offset;
159        }
160        let max_r = self.offset + self.data.len();
161        let shift = (g_len - 1) << k;
162        r = r.saturating_sub(shift).min(max_r);
163        if l < r {
164            let mut res = Shifted::default();
165            if l > 0 {
166                let f = self.truncate(0, l);
167                let f = f.step::<C>(s, k - 1, a, b, pow, g_len);
168                res = f.step::<C>(s + (1usize << (k - 1)), k - 1, a, b, pow, g_len);
169            }
170            let f = self.truncate(l, r);
171            let g = f.mul::<C>(&pow[k]);
172            res = res.add(&g);
173            if r < max_r {
174                let f = self.truncate(r, !0usize);
175                let f = f.step::<C>(s, k - 1, a, b, pow, g_len);
176                let tail = f.step::<C>(s + (1usize << (k - 1)), k - 1, a, b, pow, g_len);
177                res = res.add(&tail);
178            }
179            res
180        } else {
181            let next = self.step::<C>(s, k - 1, a, b, pow, g_len);
182            next.step::<C>(s + (1usize << (k - 1)), k - 1, a, b, pow, g_len)
183        }
184    }
Source

fn mul<C>(&self, other: &Self) -> Self
where C: ConvolveSteps<T = Vec<MInt<M>>>,

Examples found in repository?
crates/competitive/src/algorithm/number_of_increasing_sequences_between.rs (line 150)
134    fn step<C>(
135        self,
136        s: usize,
137        k: usize,
138        a: &[usize],
139        b: &[usize],
140        pow: &[Self],
141        g_len: usize,
142    ) -> Self
143    where
144        C: ConvolveSteps<T = Vec<MInt<M>>>,
145    {
146        if self.data.is_empty() {
147            return self;
148        }
149        if k == 0 {
150            let res = self.mul::<C>(&pow[0]);
151            return res.truncate(a[s + 1], b[s + 1]);
152        }
153        let len = 1usize << k;
154        let t = s + len;
155        let mut l = a[t];
156        let mut r = b[t];
157        if l < self.offset {
158            l = self.offset;
159        }
160        let max_r = self.offset + self.data.len();
161        let shift = (g_len - 1) << k;
162        r = r.saturating_sub(shift).min(max_r);
163        if l < r {
164            let mut res = Shifted::default();
165            if l > 0 {
166                let f = self.truncate(0, l);
167                let f = f.step::<C>(s, k - 1, a, b, pow, g_len);
168                res = f.step::<C>(s + (1usize << (k - 1)), k - 1, a, b, pow, g_len);
169            }
170            let f = self.truncate(l, r);
171            let g = f.mul::<C>(&pow[k]);
172            res = res.add(&g);
173            if r < max_r {
174                let f = self.truncate(r, !0usize);
175                let f = f.step::<C>(s, k - 1, a, b, pow, g_len);
176                let tail = f.step::<C>(s + (1usize << (k - 1)), k - 1, a, b, pow, g_len);
177                res = res.add(&tail);
178            }
179            res
180        } else {
181            let next = self.step::<C>(s, k - 1, a, b, pow, g_len);
182            next.step::<C>(s + (1usize << (k - 1)), k - 1, a, b, pow, g_len)
183        }
184    }
185}
186
187fn calc<M, C>(a: &[usize], b: &[usize], f: &[MInt<M>], g: &[MInt<M>]) -> Vec<MInt<M>>
188where
189    M: MIntBase,
190    C: ConvolveSteps<T = Vec<MInt<M>>>,
191{
192    if g.is_empty() {
193        return vec![];
194    }
195    let g_len = g.len();
196    let mut a = a.to_vec();
197    let mut b = b.to_vec();
198    let n = a.len();
199    for i in 1..n {
200        if a[i] < a[i - 1] {
201            a[i] = a[i - 1];
202        }
203        let limit = b[i - 1].saturating_add(g_len - 1);
204        if b[i] > limit {
205            b[i] = limit;
206        }
207    }
208    for i in (1..n).rev() {
209        let limit = a[i].saturating_sub(g_len - 1);
210        if a[i - 1] < limit {
211            a[i - 1] = limit;
212        }
213        if b[i - 1] > b[i] {
214            b[i - 1] = b[i];
215        }
216    }
217    if a.iter().zip(b.iter()).any(|(&l, &r)| l >= r) {
218        return vec![];
219    }
220    let k = a.len().next_power_of_two().trailing_zeros() as usize;
221    let mut pow: Vec<Shifted<M>> = Vec::with_capacity(k + 1);
222    pow.push(Shifted::new(0, g.to_vec()));
223    for i in 1..k {
224        let prev = pow[i - 1].clone();
225        pow.push(prev.mul::<C>(&prev));
226    }
227    let mut pos = 0usize;
228    let mut state = Shifted::new(0, f.to_vec());
229    state = state.truncate(a[0], b[0]);
230    for i in (0..k).rev() {
231        let step_len = 1usize << i;
232        if pos + step_len < a.len() {
233            state = state.step::<C>(pos, i, &a, &b, &pow, g_len);
234            pos += step_len;
235        }
236    }
237    let mut res = vec![MInt::<M>::zero(); state.offset];
238    res.extend_from_slice(&state.data);
239    res
240}
Source

fn truncate(&self, l: usize, r: usize) -> Self

Examples found in repository?
crates/competitive/src/algorithm/number_of_increasing_sequences_between.rs (line 151)
134    fn step<C>(
135        self,
136        s: usize,
137        k: usize,
138        a: &[usize],
139        b: &[usize],
140        pow: &[Self],
141        g_len: usize,
142    ) -> Self
143    where
144        C: ConvolveSteps<T = Vec<MInt<M>>>,
145    {
146        if self.data.is_empty() {
147            return self;
148        }
149        if k == 0 {
150            let res = self.mul::<C>(&pow[0]);
151            return res.truncate(a[s + 1], b[s + 1]);
152        }
153        let len = 1usize << k;
154        let t = s + len;
155        let mut l = a[t];
156        let mut r = b[t];
157        if l < self.offset {
158            l = self.offset;
159        }
160        let max_r = self.offset + self.data.len();
161        let shift = (g_len - 1) << k;
162        r = r.saturating_sub(shift).min(max_r);
163        if l < r {
164            let mut res = Shifted::default();
165            if l > 0 {
166                let f = self.truncate(0, l);
167                let f = f.step::<C>(s, k - 1, a, b, pow, g_len);
168                res = f.step::<C>(s + (1usize << (k - 1)), k - 1, a, b, pow, g_len);
169            }
170            let f = self.truncate(l, r);
171            let g = f.mul::<C>(&pow[k]);
172            res = res.add(&g);
173            if r < max_r {
174                let f = self.truncate(r, !0usize);
175                let f = f.step::<C>(s, k - 1, a, b, pow, g_len);
176                let tail = f.step::<C>(s + (1usize << (k - 1)), k - 1, a, b, pow, g_len);
177                res = res.add(&tail);
178            }
179            res
180        } else {
181            let next = self.step::<C>(s, k - 1, a, b, pow, g_len);
182            next.step::<C>(s + (1usize << (k - 1)), k - 1, a, b, pow, g_len)
183        }
184    }
185}
186
187fn calc<M, C>(a: &[usize], b: &[usize], f: &[MInt<M>], g: &[MInt<M>]) -> Vec<MInt<M>>
188where
189    M: MIntBase,
190    C: ConvolveSteps<T = Vec<MInt<M>>>,
191{
192    if g.is_empty() {
193        return vec![];
194    }
195    let g_len = g.len();
196    let mut a = a.to_vec();
197    let mut b = b.to_vec();
198    let n = a.len();
199    for i in 1..n {
200        if a[i] < a[i - 1] {
201            a[i] = a[i - 1];
202        }
203        let limit = b[i - 1].saturating_add(g_len - 1);
204        if b[i] > limit {
205            b[i] = limit;
206        }
207    }
208    for i in (1..n).rev() {
209        let limit = a[i].saturating_sub(g_len - 1);
210        if a[i - 1] < limit {
211            a[i - 1] = limit;
212        }
213        if b[i - 1] > b[i] {
214            b[i - 1] = b[i];
215        }
216    }
217    if a.iter().zip(b.iter()).any(|(&l, &r)| l >= r) {
218        return vec![];
219    }
220    let k = a.len().next_power_of_two().trailing_zeros() as usize;
221    let mut pow: Vec<Shifted<M>> = Vec::with_capacity(k + 1);
222    pow.push(Shifted::new(0, g.to_vec()));
223    for i in 1..k {
224        let prev = pow[i - 1].clone();
225        pow.push(prev.mul::<C>(&prev));
226    }
227    let mut pos = 0usize;
228    let mut state = Shifted::new(0, f.to_vec());
229    state = state.truncate(a[0], b[0]);
230    for i in (0..k).rev() {
231        let step_len = 1usize << i;
232        if pos + step_len < a.len() {
233            state = state.step::<C>(pos, i, &a, &b, &pow, g_len);
234            pos += step_len;
235        }
236    }
237    let mut res = vec![MInt::<M>::zero(); state.offset];
238    res.extend_from_slice(&state.data);
239    res
240}
Source

fn step<C>( self, s: usize, k: usize, a: &[usize], b: &[usize], pow: &[Self], g_len: usize, ) -> Self
where C: ConvolveSteps<T = Vec<MInt<M>>>,

Examples found in repository?
crates/competitive/src/algorithm/number_of_increasing_sequences_between.rs (line 167)
134    fn step<C>(
135        self,
136        s: usize,
137        k: usize,
138        a: &[usize],
139        b: &[usize],
140        pow: &[Self],
141        g_len: usize,
142    ) -> Self
143    where
144        C: ConvolveSteps<T = Vec<MInt<M>>>,
145    {
146        if self.data.is_empty() {
147            return self;
148        }
149        if k == 0 {
150            let res = self.mul::<C>(&pow[0]);
151            return res.truncate(a[s + 1], b[s + 1]);
152        }
153        let len = 1usize << k;
154        let t = s + len;
155        let mut l = a[t];
156        let mut r = b[t];
157        if l < self.offset {
158            l = self.offset;
159        }
160        let max_r = self.offset + self.data.len();
161        let shift = (g_len - 1) << k;
162        r = r.saturating_sub(shift).min(max_r);
163        if l < r {
164            let mut res = Shifted::default();
165            if l > 0 {
166                let f = self.truncate(0, l);
167                let f = f.step::<C>(s, k - 1, a, b, pow, g_len);
168                res = f.step::<C>(s + (1usize << (k - 1)), k - 1, a, b, pow, g_len);
169            }
170            let f = self.truncate(l, r);
171            let g = f.mul::<C>(&pow[k]);
172            res = res.add(&g);
173            if r < max_r {
174                let f = self.truncate(r, !0usize);
175                let f = f.step::<C>(s, k - 1, a, b, pow, g_len);
176                let tail = f.step::<C>(s + (1usize << (k - 1)), k - 1, a, b, pow, g_len);
177                res = res.add(&tail);
178            }
179            res
180        } else {
181            let next = self.step::<C>(s, k - 1, a, b, pow, g_len);
182            next.step::<C>(s + (1usize << (k - 1)), k - 1, a, b, pow, g_len)
183        }
184    }
185}
186
187fn calc<M, C>(a: &[usize], b: &[usize], f: &[MInt<M>], g: &[MInt<M>]) -> Vec<MInt<M>>
188where
189    M: MIntBase,
190    C: ConvolveSteps<T = Vec<MInt<M>>>,
191{
192    if g.is_empty() {
193        return vec![];
194    }
195    let g_len = g.len();
196    let mut a = a.to_vec();
197    let mut b = b.to_vec();
198    let n = a.len();
199    for i in 1..n {
200        if a[i] < a[i - 1] {
201            a[i] = a[i - 1];
202        }
203        let limit = b[i - 1].saturating_add(g_len - 1);
204        if b[i] > limit {
205            b[i] = limit;
206        }
207    }
208    for i in (1..n).rev() {
209        let limit = a[i].saturating_sub(g_len - 1);
210        if a[i - 1] < limit {
211            a[i - 1] = limit;
212        }
213        if b[i - 1] > b[i] {
214            b[i - 1] = b[i];
215        }
216    }
217    if a.iter().zip(b.iter()).any(|(&l, &r)| l >= r) {
218        return vec![];
219    }
220    let k = a.len().next_power_of_two().trailing_zeros() as usize;
221    let mut pow: Vec<Shifted<M>> = Vec::with_capacity(k + 1);
222    pow.push(Shifted::new(0, g.to_vec()));
223    for i in 1..k {
224        let prev = pow[i - 1].clone();
225        pow.push(prev.mul::<C>(&prev));
226    }
227    let mut pos = 0usize;
228    let mut state = Shifted::new(0, f.to_vec());
229    state = state.truncate(a[0], b[0]);
230    for i in (0..k).rev() {
231        let step_len = 1usize << i;
232        if pos + step_len < a.len() {
233            state = state.step::<C>(pos, i, &a, &b, &pow, g_len);
234            pos += step_len;
235        }
236    }
237    let mut res = vec![MInt::<M>::zero(); state.offset];
238    res.extend_from_slice(&state.data);
239    res
240}

Trait Implementations§

Source§

impl<M> Clone for Shifted<M>
where M: MIntBase,

Source§

fn clone(&self) -> Self

Returns a duplicate of the value. Read more
1.0.0 · Source§

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source. Read more
Source§

impl<M> Default for Shifted<M>
where M: MIntBase,

Source§

fn default() -> Self

Returns the “default value” for a type. Read more

Auto Trait Implementations§

§

impl<M> Freeze for Shifted<M>

§

impl<M> RefUnwindSafe for Shifted<M>
where <M as MIntBase>::Inner: RefUnwindSafe,

§

impl<M> Send for Shifted<M>
where <M as MIntBase>::Inner: Send,

§

impl<M> Sync for Shifted<M>
where <M as MIntBase>::Inner: Sync,

§

impl<M> Unpin for Shifted<M>
where <M as MIntBase>::Inner: Unpin,

§

impl<M> UnsafeUnpin for Shifted<M>

§

impl<M> UnwindSafe for Shifted<M>
where <M as MIntBase>::Inner: UnwindSafe,

Blanket Implementations§

Source§

impl<T> Any for T
where T: 'static + ?Sized,

Source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
Source§

impl<T> Borrow<T> for T
where T: ?Sized,

Source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
Source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

Source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
Source§

impl<T> CloneToUninit for T
where T: Clone,

Source§

unsafe fn clone_to_uninit(&self, dest: *mut u8)

🔬This is a nightly-only experimental API. (clone_to_uninit)
Performs copy-assignment from self to dest. Read more
Source§

impl<T> From<T> for T

Source§

fn from(t: T) -> T

Returns the argument unchanged.

Source§

impl<T, U> Into<U> for T
where U: From<T>,

Source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

Source§

impl<T> ToArrayVecScalar for T

Source§

fn to_array_vec_scalar(self) -> ArrayVecScalar<T>

Source§

impl<T> ToOwned for T
where T: Clone,

Source§

type Owned = T

The resulting type after obtaining ownership.
Source§

fn to_owned(&self) -> T

Creates owned data from borrowed data, usually by cloning. Read more
Source§

fn clone_into(&self, target: &mut T)

Uses borrowed data to replace owned data, usually by cloning. Read more
Source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

Source§

type Error = Infallible

The type returned in the event of a conversion error.
Source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

Performs the conversion.
Source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

Source§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
Source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.