1use super::{
2 Convolve998244353, ConvolveSteps, MInt, MIntBase, One, Zero,
3 montgomery::{MInt998244353, Modulo998244353},
4};
5
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}
43
44pub fn number_of_increasing_sequences_between_998244353(a: &[usize], b: &[usize]) -> MInt998244353 {
45 number_of_increasing_sequences_between::<Modulo998244353, Convolve998244353>(a, b)
46}
47
48struct Shifted<M>
49where
50 M: MIntBase,
51{
52 offset: usize,
53 data: Vec<MInt<M>>,
54}
55
56impl<M> Clone for Shifted<M>
57where
58 M: MIntBase,
59{
60 fn clone(&self) -> Self {
61 Self {
62 offset: self.offset,
63 data: self.data.clone(),
64 }
65 }
66}
67
68impl<M> Default for Shifted<M>
69where
70 M: MIntBase,
71{
72 fn default() -> Self {
73 Self {
74 offset: 0,
75 data: Vec::new(),
76 }
77 }
78}
79
80impl<M> Shifted<M>
81where
82 M: MIntBase,
83{
84 fn new(offset: usize, data: Vec<MInt<M>>) -> Self {
85 Self { offset, data }
86 }
87
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}
241
242#[cfg(test)]
243mod tests {
244 use super::*;
245 use crate::{rand, tools::Xorshift};
246 use std::collections::HashMap;
247
248 fn naive(a: &[usize], b: &[usize]) -> MInt998244353 {
249 let mut dp = HashMap::new();
250 dp.insert(0, MInt998244353::one());
251 for (&l, &r) in a.iter().zip(b.iter()) {
252 let mut next = HashMap::new();
253 for (&x, &count) in dp.iter() {
254 for y in l.max(x)..r {
255 *next.entry(y).or_default() += count;
256 }
257 }
258 dp = next;
259 }
260 dp.values().sum()
261 }
262
263 #[test]
264 fn test_number_of_increasing_sequences_between_998244353() {
265 let mut rng = Xorshift::default();
266 for _ in 0..300 {
267 let n = rng.random(1usize..300);
268 let max = rng.random(1usize..300);
269 rand!(rng, mut a: [0usize..=max; n], mut b: [0usize..=max; n]);
270 for i in 0..n {
271 if a[i] > b[i] {
272 std::mem::swap(&mut a[i], &mut b[i]);
273 }
274 }
275 let result = number_of_increasing_sequences_between_998244353(&a, &b);
276 let expected = naive(&a, &b);
277 assert_eq!(result, expected);
278 }
279 }
280}