Struct FormalPowerSeries

Source

pub struct FormalPowerSeries<T, C> {
    pub data: Vec<T>,
    /* private fields */
}

Fields§

§data: Vec<T>

Implementations§

Source §

impl<T, C> FormalPowerSeries<T, C>

Source

pub fn from_vec(data: Vec<T>) -> Self

Examples found in repository ?

crates/competitive/src/math/formal_power_series/formal_power_series_impls.rs (line 38)

37    fn clone(&self) -> Self {
38        Self::from_vec(self.data.clone())
39    }
40}
41impl<T, C> PartialEq for FormalPowerSeries<T, C>
42where
43    T: PartialEq,
44{
45    fn eq(&self, other: &Self) -> bool {
46        self.data.eq(&other.data)
47    }
48}
49impl<T, C> Eq for FormalPowerSeries<T, C> where T: PartialEq {}
50
51impl<T, C> FormalPowerSeries<T, C>
52where
53    T: Zero,
54{
55    pub fn zeros(deg: usize) -> Self {
56        repeat_with(T::zero).take(deg).collect()
57    }
58    pub fn resize(&mut self, deg: usize) {
59        self.data.resize_with(deg, Zero::zero)
60    }
61    pub fn resized(mut self, deg: usize) -> Self {
62        self.resize(deg);
63        self
64    }
65    pub fn reversed(mut self) -> Self {
66        self.data.reverse();
67        self
68    }
69}
70
71impl<T, C> FormalPowerSeries<T, C>
72where
73    T: Zero + PartialEq,
74{
75    pub fn trim_tail_zeros(&mut self) {
76        let mut len = self.length();
77        while len > 0 {
78            if self.data[len - 1].is_zero() {
79                len -= 1;
80            } else {
81                break;
82            }
83        }
84        self.truncate(len);
85    }
86}
87
88impl<T, C> Zero for FormalPowerSeries<T, C>
89where
90    T: PartialEq,
91{
92    fn zero() -> Self {
93        Self::from_vec(Vec::new())
94    }
95}
96impl<T, C> One for FormalPowerSeries<T, C>
97where
98    T: PartialEq + One,
99{
100    fn one() -> Self {
101        Self::from(T::one())
102    }
103}
104
105impl<T, C> IntoIterator for FormalPowerSeries<T, C> {
106    type Item = T;
107    type IntoIter = std::vec::IntoIter<T>;
108    fn into_iter(self) -> Self::IntoIter {
109        self.data.into_iter()
110    }
111}
112impl<'a, T, C> IntoIterator for &'a FormalPowerSeries<T, C> {
113    type Item = &'a T;
114    type IntoIter = Iter<'a, T>;
115    fn into_iter(self) -> Self::IntoIter {
116        self.data.iter()
117    }
118}
119impl<'a, T, C> IntoIterator for &'a mut FormalPowerSeries<T, C> {
120    type Item = &'a mut T;
121    type IntoIter = IterMut<'a, T>;
122    fn into_iter(self) -> Self::IntoIter {
123        self.data.iter_mut()
124    }
125}
126
127impl<T, C> FromIterator<T> for FormalPowerSeries<T, C> {
128    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
129        Self::from_vec(iter.into_iter().collect())
130    }
131}
132
133impl<T, C> Index<usize> for FormalPowerSeries<T, C> {
134    type Output = T;
135    fn index(&self, index: usize) -> &Self::Output {
136        &self.data[index]
137    }
138}
139impl<T, C> IndexMut<usize> for FormalPowerSeries<T, C> {
140    fn index_mut(&mut self, index: usize) -> &mut Self::Output {
141        &mut self.data[index]
142    }
143}
144
145impl<T, C> From<T> for FormalPowerSeries<T, C> {
146    fn from(x: T) -> Self {
147        once(x).collect()
148    }
149}
150impl<T, C> From<Vec<T>> for FormalPowerSeries<T, C> {
151    fn from(data: Vec<T>) -> Self {
152        Self::from_vec(data)
153    }
154}
155
156impl<T, C> FormalPowerSeries<T, C>
157where
158    T: FormalPowerSeriesCoefficient,
159{
160    pub fn prefix_ref(&self, deg: usize) -> Self {
161        if deg < self.length() {
162            Self::from_vec(self.data[..deg].to_vec())
163        } else {
164            self.clone()
165        }
166    }
167    pub fn prefix(mut self, deg: usize) -> Self {
168        self.data.truncate(deg);
169        self
170    }
171    pub fn even(mut self) -> Self {
172        let mut keep = false;
173        self.data.retain(|_| {
174            keep = !keep;
175            keep
176        });
177        self
178    }
179    pub fn odd(mut self) -> Self {
180        let mut keep = true;
181        self.data.retain(|_| {
182            keep = !keep;
183            keep
184        });
185        self
186    }
187    pub fn diff(mut self) -> Self {
188        let mut c = T::one();
189        for x in self.iter_mut().skip(1) {
190            *x *= &c;
191            c += T::one();
192        }
193        if self.length() > 0 {
194            self.data.remove(0);
195        }
196        self
197    }
198    pub fn integral(mut self) -> Self {
199        let n = self.length();
200        self.data.insert(0, Zero::zero());
201        let mut fact = Vec::with_capacity(n + 1);
202        let mut c = T::one();
203        fact.push(c.clone());
204        for _ in 1..n {
205            fact.push(fact.last().cloned().unwrap() * c.clone());
206            c += T::one();
207        }
208        let mut invf = T::one() / (fact.last().cloned().unwrap() * c.clone());
209        for x in self.iter_mut().skip(1).rev() {
210            *x *= invf.clone() * fact.pop().unwrap();
211            invf *= c.clone();
212            c -= T::one();
213        }
214        self
215    }
216    pub fn parity_inversion(mut self) -> Self {
217        self.iter_mut()
218            .skip(1)
219            .step_by(2)
220            .for_each(|x| *x = -x.clone());
221        self
222    }
223    pub fn eval(&self, x: T) -> T {
224        let mut base = T::one();
225        let mut res = T::zero();
226        for a in self.iter() {
227            res += base.clone() * a.clone();
228            base *= x.clone();
229        }
230        res
231    }
232}
233
234impl<T, C> FormalPowerSeries<T, C>
235where
236    T: FormalPowerSeriesCoefficient,
237    C: ConvolveSteps<T = Vec<T>>,
238{
239    pub fn inv(&self, deg: usize) -> Self {
240        debug_assert!(!self[0].is_zero());
241        let mut f = Self::from(T::one() / self[0].clone());
242        let mut i = 1;
243        while i < deg {
244            let g = self.prefix_ref((i * 2).min(deg));
245            let h = f.clone();
246            let mut g = C::transform(g.data, 2 * i);
247            let h = C::transform(h.data, 2 * i);
248            C::multiply(&mut g, &h);
249            let mut g = Self::from_vec(C::inverse_transform(g, 2 * i));
250            g >>= i;
251            let mut g = C::transform(g.data, 2 * i);
252            C::multiply(&mut g, &h);
253            let g = Self::from_vec(C::inverse_transform(g, 2 * i));
254            f.data.extend((-g).into_iter().take(i));
255            i *= 2;
256        }
257        f.truncate(deg);
258        f
259    }
260    pub fn exp(&self, deg: usize) -> Self {
261        debug_assert!(self[0].is_zero());
262        let mut f = Self::one();
263        let mut i = 1;
264        while i < deg {
265            let mut g = -f.log(i * 2);
266            g[0] += T::one();
267            for (g, x) in g.iter_mut().zip(self.iter().take(i * 2)) {
268                *g += x.clone();
269            }
270            f = (f * g).prefix(i * 2);
271            i *= 2;
272        }
273        f.prefix(deg)
274    }
275    pub fn log(&self, deg: usize) -> Self {
276        (self.inv(deg) * self.clone().diff()).integral().prefix(deg)
277    }
278    pub fn pow(&self, rhs: usize, deg: usize) -> Self {
279        if rhs == 0 {
280            return Self::from_vec(
281                once(T::one())
282                    .chain(repeat_with(T::zero))
283                    .take(deg)
284                    .collect(),
285            );
286        }
287        if let Some(k) = self.iter().position(|x| !x.is_zero()) {
288            if k >= (deg + rhs - 1) / rhs {
289                Self::zeros(deg)
290            } else {
291                let mut x0 = self[k].clone();
292                let rev = T::one() / x0.clone();
293                let x = {
294                    let mut x = T::one();
295                    let mut y = rhs;
296                    while y > 0 {
297                        if y & 1 == 1 {
298                            x *= x0.clone();
299                        }
300                        x0 *= x0.clone();
301                        y >>= 1;
302                    }
303                    x
304                };
305                let mut f = (self.clone() * &rev) >> k;
306                f = (f.log(deg) * &T::from(rhs)).exp(deg) * &x;
307                f.truncate(deg - k * rhs);
308                f <<= k * rhs;
309                f
310            }
311        } else {
312            Self::zeros(deg)
313        }
314    }
315}
316
317impl<T, C> FormalPowerSeries<T, C>
318where
319    T: FormalPowerSeriesCoefficientSqrt,
320    C: ConvolveSteps<T = Vec<T>>,
321{
322    pub fn sqrt(&self, deg: usize) -> Option<Self> {
323        if self[0].is_zero() {
324            if let Some(k) = self.iter().position(|x| !x.is_zero()) {
325                if k % 2 != 0 {
326                    return None;
327                } else if deg > k / 2 {
328                    return Some((self >> k).sqrt(deg - k / 2)? << (k / 2));
329                }
330            }
331        } else {
332            let inv2 = T::one() / (T::one() + T::one());
333            let mut f = Self::from(self[0].sqrt_coefficient()?);
334            let mut i = 1;
335            while i < deg {
336                f = (&f + &(self.prefix_ref(i * 2) * f.inv(i * 2))).prefix(i * 2) * &inv2;
337                i *= 2;
338            }
339            f.truncate(deg);
340            return Some(f);
341        }
342        Some(Self::zeros(deg))
343    }
344}
345
346impl<T, C> FormalPowerSeries<T, C>
347where
348    T: FormalPowerSeriesCoefficient,
349    C: ConvolveSteps<T = Vec<T>>,
350{
351    pub fn count_subset_sum<F>(&self, deg: usize, mut inverse: F) -> Self
352    where
353        F: FnMut(usize) -> T,
354    {
355        let n = self.length();
356        let mut f = Self::zeros(n);
357        for i in 1..n {
358            if !self[i].is_zero() {
359                for (j, d) in (0..n).step_by(i).enumerate().skip(1) {
360                    if j & 1 != 0 {
361                        f[d] += self[i].clone() * &inverse(j);
362                    } else {
363                        f[d] -= self[i].clone() * &inverse(j);
364                    }
365                }
366            }
367        }
368        f.exp(deg)
369    }
370    pub fn count_multiset_sum<F>(&self, deg: usize, mut inverse: F) -> Self
371    where
372        F: FnMut(usize) -> T,
373    {
374        let n = self.length();
375        let mut f = Self::zeros(n);
376        for i in 1..n {
377            if !self[i].is_zero() {
378                for (j, d) in (0..n).step_by(i).enumerate().skip(1) {
379                    f[d] += self[i].clone() * &inverse(j);
380                }
381            }
382        }
383        f.exp(deg)
384    }
385    /// [x^n] P(x) / Q(x)
386    pub fn bostan_mori(self, rhs: Self, mut n: usize) -> T {
387        let mut p = self;
388        let mut q = rhs;
389        while n > 0 {
390            let mq = q.clone().parity_inversion();
391            let u = p * mq.clone();
392            p = if n % 2 == 0 { u.even() } else { u.odd() };
393            q = (q * mq).even();
394            n /= 2;
395        }
396        p[0].clone() / q[0].clone()
397    }
398    /// return F(x) where [x^n] P(x) / Q(x) = [x^d-1] P(x) F(x)
399    pub fn bostan_mori_msb(self, n: usize) -> Self {
400        let d = self.length() - 1;
401        if n == 0 {
402            return (Self::one() << (d - 1)) / self[0].clone();
403        }
404        let q = self;
405        let mq = q.clone().parity_inversion();
406        let w = (q * &mq).even().bostan_mori_msb(n / 2);
407        let mut s = Self::zeros(w.length() * 2 - (n % 2));
408        for (i, x) in w.iter().enumerate() {
409            s[i * 2 + (1 - n % 2)] = x.clone();
410        }
411        let len = 2 * d + 1;
412        let ts = C::transform(s.prefix(len).data, len);
413        mq.reversed().middle_product(&ts, len).prefix(d + 1)
414    }
415    /// x^n mod self
416    pub fn pow_mod(self, n: usize) -> Self {
417        let d = self.length() - 1;
418        let q = self.reversed();
419        let u = q.clone().bostan_mori_msb(n);
420        let mut f = (u * q).prefix(d).reversed();
421        f.trim_tail_zeros();
422        f
423    }
424    fn middle_product(self, other: &C::F, deg: usize) -> Self {
425        let n = self.length();
426        let mut s = C::transform(self.reversed().data, deg);
427        C::multiply(&mut s, other);
428        Self::from_vec((C::inverse_transform(s, deg))[n - 1..].to_vec())
429    }
430    pub fn multipoint_evaluation(self, points: &[T]) -> Vec<T> {
431        let n = points.len();
432        if n <= 32 {
433            return points.iter().map(|p| self.eval(p.clone())).collect();
434        }
435        let mut subproduct_tree = Vec::with_capacity(n * 2);
436        subproduct_tree.resize_with(n, Zero::zero);
437        for x in points {
438            subproduct_tree.push(Self::from_vec(vec![-x.clone(), T::one()]));
439        }
440        for i in (1..n).rev() {
441            subproduct_tree[i] = &subproduct_tree[i * 2] * &subproduct_tree[i * 2 + 1];
442        }
443        let mut uptree_t = Vec::with_capacity(n * 2);
444        uptree_t.resize_with(1, Zero::zero);
445        subproduct_tree.reverse();
446        subproduct_tree.pop();
447        let m = self.length();
448        let v = subproduct_tree.pop().unwrap().reversed().resized(m);
449        let s = C::transform(self.data, m * 2);
450        uptree_t.push(v.inv(m).middle_product(&s, m * 2).resized(n).reversed());
451        for i in 1..n {
452            let subl = subproduct_tree.pop().unwrap();
453            let subr = subproduct_tree.pop().unwrap();
454            let (dl, dr) = (subl.length(), subr.length());
455            let len = dl.max(dr) + uptree_t[i].length();
456            let s = C::transform(uptree_t[i].data.to_vec(), len);
457            uptree_t.push(subr.middle_product(&s, len).prefix(dl));
458            uptree_t.push(subl.middle_product(&s, len).prefix(dr));
459        }
460        uptree_t[n..]
461            .iter()
462            .map(|u| u.data.first().cloned().unwrap_or_else(Zero::zero))
463            .collect()
464    }
465    pub fn product_all<I>(iter: I, deg: usize) -> Self
466    where
467        I: IntoIterator<Item = Self>,
468    {
469        let mut heap: BinaryHeap<_> = iter
470            .into_iter()
471            .map(|f| PartialIgnoredOrd(Reverse(f.length()), f))
472            .collect();
473        while let Some(PartialIgnoredOrd(_, x)) = heap.pop() {
474            if let Some(PartialIgnoredOrd(_, y)) = heap.pop() {
475                let z = (x * y).prefix(deg);
476                heap.push(PartialIgnoredOrd(Reverse(z.length()), z));
477            } else {
478                return x;
479            }
480        }
481        Self::one()
482    }
483    pub fn sum_all_rational<I>(iter: I, deg: usize) -> (Self, Self)
484    where
485        I: IntoIterator<Item = (Self, Self)>,
486    {
487        let mut heap: BinaryHeap<_> = iter
488            .into_iter()
489            .map(|(f, g)| PartialIgnoredOrd(Reverse(f.length().max(g.length())), (f, g)))
490            .collect();
491        while let Some(PartialIgnoredOrd(_, (xa, xb))) = heap.pop() {
492            if let Some(PartialIgnoredOrd(_, (ya, yb))) = heap.pop() {
493                let zb = (&xb * &yb).prefix(deg);
494                let za = (xa * yb + ya * xb).prefix(deg);
495                heap.push(PartialIgnoredOrd(
496                    Reverse(za.length().max(zb.length())),
497                    (za, zb),
498                ));
499            } else {
500                return (xa, xb);
501            }
502        }
503        (Self::zero(), Self::one())
504    }
505    pub fn kth_term_of_linearly_recurrence(self, a: Vec<T>, k: usize) -> T {
506        if let Some(x) = a.get(k) {
507            return x.clone();
508        }
509        let p = (Self::from_vec(a).prefix(self.length() - 1) * &self).prefix(self.length() - 1);
510        p.bostan_mori(self, k)
511    }
512    pub fn kth_term(a: Vec<T>, k: usize) -> T {
513        if let Some(x) = a.get(k) {
514            return x.clone();
515        }
516        Self::from_vec(berlekamp_massey(&a)).kth_term_of_linearly_recurrence(a, k)
517    }
518    /// sum_i a_i exp(b_i x)
519    pub fn linear_sum_of_exp<I, F>(iter: I, deg: usize, mut inv_fact: F) -> Self
520    where
521        I: IntoIterator<Item = (T, T)>,
522        F: FnMut(usize) -> T,
523    {
524        let (p, q) = Self::sum_all_rational(
525            iter.into_iter()
526                .map(|(a, b)| (Self::from_vec(vec![a]), Self::from_vec(vec![T::one(), -b]))),
527            deg,
528        );
529        let mut f = (p * q.inv(deg)).prefix(deg);
530        for i in 0..f.length() {
531            f[i] *= inv_fact(i);
532        }
533        f
534    }
535}
536
537impl<M, C> FormalPowerSeries<MInt<M>, C>
538where
539    M: MIntConvert<usize>,
540    C: ConvolveSteps<T = Vec<MInt<M>>>,
541{
542    /// f(x) <- f(x + a)
543    pub fn taylor_shift(mut self, a: MInt<M>, f: &MemorizedFactorial<M>) -> Self {
544        let n = self.length();
545        for i in 0..n {
546            self.data[i] *= f.fact[i];
547        }
548        self.data.reverse();
549        let mut b = a;
550        let mut g = Self::from_vec(f.inv_fact[..n].to_vec());
551        for i in 1..n {
552            g[i] *= b;
553            b *= a;
554        }
555        self *= g;
556        self.truncate(n);
557        self.data.reverse();
558        for i in 0..n {
559            self.data[i] *= f.inv_fact[i];
560        }
561        self
562    }

More examples

Hide additional examples

crates/competitive/src/math/formal_power_series/formal_power_series_nums.rs (line 202)

201    fn mul(self, rhs: Self) -> Self::Output {
202        Self::from_vec(C::convolve(self.data, rhs.data))
203    }

crates/library_checker/src/polynomial/exp_of_formal_power_series.rs (line 10)

6pub fn exp_of_formal_power_series(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, n, a: [MInt998244353; n]);
10    let f = Fps998244353::from_vec(a);
11    let g = f.exp(n);
12    iter_print!(writer, @it g.data);
13}

crates/library_checker/src/polynomial/inv_of_formal_power_series.rs (line 10)

6pub fn inv_of_formal_power_series(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, n, a: [MInt998244353; n]);
10    let f = Fps998244353::from_vec(a);
11    let g = f.inv(n);
12    iter_print!(writer, @it g.data);
13}

crates/library_checker/src/polynomial/log_of_formal_power_series.rs (line 10)

6pub fn log_of_formal_power_series(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, n, a: [MInt998244353; n]);
10    let f = Fps998244353::from_vec(a);
11    let g = f.log(n);
12    iter_print!(writer, @it g.data);
13}

crates/library_checker/src/polynomial/pow_of_formal_power_series.rs (line 10)

6pub fn pow_of_formal_power_series(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, n, m, a: [MInt998244353; n]);
10    let f = Fps998244353::from_vec(a);
11    let g = f.pow(m, n);
12    iter_print!(writer, @it g.data);
13}

Additional examples can be found in:

Source

pub fn length(&self) -> usize

Examples found in repository ?

crates/competitive/src/math/formal_power_series/formal_power_series_nums.rs (line 17)

16    fn add_assign(&mut self, rhs: T) {
17        if self.length() == 0 {
18            self.data.push(T::zero());
19        }
20        self.data[0].add_assign(rhs);
21    }
22}
23impl<T, C> SubAssign<T> for FormalPowerSeries<T, C>
24where
25    T: FormalPowerSeriesCoefficient,
26{
27    fn sub_assign(&mut self, rhs: T) {
28        if self.length() == 0 {
29            self.data.push(T::zero());
30        }
31        self.data[0].sub_assign(rhs);
32        self.trim_tail_zeros();
33    }
34}
35impl<T, C> MulAssign<T> for FormalPowerSeries<T, C>
36where
37    T: FormalPowerSeriesCoefficient,
38{
39    fn mul_assign(&mut self, rhs: T) {
40        for x in self.iter_mut() {
41            x.mul_assign(&rhs);
42        }
43    }
44}
45impl<T, C> DivAssign<T> for FormalPowerSeries<T, C>
46where
47    T: FormalPowerSeriesCoefficient,
48{
49    fn div_assign(&mut self, rhs: T) {
50        let rinv = T::one() / rhs;
51        for x in self.iter_mut() {
52            x.mul_assign(&rinv);
53        }
54    }
55}
56macro_rules! impl_fps_single_binop {
57    ($imp:ident, $method:ident, $imp_assign:ident, $method_assign:ident) => {
58        impl<T, C> $imp_assign<&T> for FormalPowerSeries<T, C>
59        where
60            T: FormalPowerSeriesCoefficient,
61        {
62            fn $method_assign(&mut self, rhs: &T) {
63                $imp_assign::$method_assign(self, rhs.clone());
64            }
65        }
66        impl<T, C> $imp<T> for FormalPowerSeries<T, C>
67        where
68            T: FormalPowerSeriesCoefficient,
69        {
70            type Output = Self;
71            fn $method(mut self, rhs: T) -> Self::Output {
72                $imp_assign::$method_assign(&mut self, rhs);
73                self
74            }
75        }
76        impl<T, C> $imp<&T> for FormalPowerSeries<T, C>
77        where
78            T: FormalPowerSeriesCoefficient,
79        {
80            type Output = Self;
81            fn $method(mut self, rhs: &T) -> Self::Output {
82                $imp_assign::$method_assign(&mut self, rhs);
83                self
84            }
85        }
86        impl<T, C> $imp<T> for &FormalPowerSeries<T, C>
87        where
88            T: FormalPowerSeriesCoefficient,
89        {
90            type Output = FormalPowerSeries<T, C>;
91            fn $method(self, rhs: T) -> Self::Output {
92                $imp::$method(self.clone(), rhs)
93            }
94        }
95        impl<T, C> $imp<&T> for &FormalPowerSeries<T, C>
96        where
97            T: FormalPowerSeriesCoefficient,
98        {
99            type Output = FormalPowerSeries<T, C>;
100            fn $method(self, rhs: &T) -> Self::Output {
101                $imp::$method(self.clone(), rhs)
102            }
103        }
104    };
105}
106impl_fps_single_binop!(Add, add, AddAssign, add_assign);
107impl_fps_single_binop!(Sub, sub, SubAssign, sub_assign);
108impl_fps_single_binop!(Mul, mul, MulAssign, mul_assign);
109impl_fps_single_binop!(Div, div, DivAssign, div_assign);
110
111impl<T, C> AddAssign<&Self> for FormalPowerSeries<T, C>
112where
113    T: FormalPowerSeriesCoefficient,
114{
115    fn add_assign(&mut self, rhs: &Self) {
116        if self.length() < rhs.length() {
117            self.resize(rhs.length());
118        }
119        for (x, y) in self.iter_mut().zip(rhs.iter()) {
120            x.add_assign(y);
121        }
122    }
123}
124impl<T, C> SubAssign<&Self> for FormalPowerSeries<T, C>
125where
126    T: FormalPowerSeriesCoefficient,
127{
128    fn sub_assign(&mut self, rhs: &Self) {
129        if self.length() < rhs.length() {
130            self.resize(rhs.length());
131        }
132        for (x, y) in self.iter_mut().zip(rhs.iter()) {
133            x.sub_assign(y);
134        }
135        self.trim_tail_zeros();
136    }
137}
138
139macro_rules! impl_fps_binop_addsub {
140    ($imp:ident, $method:ident, $imp_assign:ident, $method_assign:ident) => {
141        impl<T, C> $imp_assign for FormalPowerSeries<T, C>
142        where
143            T: FormalPowerSeriesCoefficient,
144        {
145            fn $method_assign(&mut self, rhs: Self) {
146                $imp_assign::$method_assign(self, &rhs);
147            }
148        }
149        impl<T, C> $imp for FormalPowerSeries<T, C>
150        where
151            T: FormalPowerSeriesCoefficient,
152        {
153            type Output = Self;
154            fn $method(mut self, rhs: Self) -> Self::Output {
155                $imp_assign::$method_assign(&mut self, &rhs);
156                self
157            }
158        }
159        impl<T, C> $imp<&FormalPowerSeries<T, C>> for FormalPowerSeries<T, C>
160        where
161            T: FormalPowerSeriesCoefficient,
162        {
163            type Output = Self;
164            fn $method(mut self, rhs: &FormalPowerSeries<T, C>) -> Self::Output {
165                $imp_assign::$method_assign(&mut self, rhs);
166                self
167            }
168        }
169        impl<T, C> $imp<FormalPowerSeries<T, C>> for &FormalPowerSeries<T, C>
170        where
171            T: FormalPowerSeriesCoefficient,
172        {
173            type Output = FormalPowerSeries<T, C>;
174            fn $method(self, rhs: FormalPowerSeries<T, C>) -> Self::Output {
175                let mut self_ = self.clone();
176                $imp_assign::$method_assign(&mut self_, &rhs);
177                self_
178            }
179        }
180        impl<T, C> $imp<&FormalPowerSeries<T, C>> for &FormalPowerSeries<T, C>
181        where
182            T: FormalPowerSeriesCoefficient,
183        {
184            type Output = FormalPowerSeries<T, C>;
185            fn $method(self, rhs: &FormalPowerSeries<T, C>) -> Self::Output {
186                let mut self_ = self.clone();
187                $imp_assign::$method_assign(&mut self_, rhs);
188                self_
189            }
190        }
191    };
192}
193impl_fps_binop_addsub!(Add, add, AddAssign, add_assign);
194impl_fps_binop_addsub!(Sub, sub, SubAssign, sub_assign);
195
196impl<T, C> Mul for FormalPowerSeries<T, C>
197where
198    C: ConvolveSteps<T = Vec<T>>,
199{
200    type Output = Self;
201    fn mul(self, rhs: Self) -> Self::Output {
202        Self::from_vec(C::convolve(self.data, rhs.data))
203    }
204}
205impl<T, C> Div for FormalPowerSeries<T, C>
206where
207    T: FormalPowerSeriesCoefficient,
208    C: ConvolveSteps<T = Vec<T>>,
209{
210    type Output = Self;
211    fn div(mut self, mut rhs: Self) -> Self::Output {
212        self.trim_tail_zeros();
213        rhs.trim_tail_zeros();
214        if self.length() < rhs.length() {
215            return Self::zero();
216        }
217        self.data.reverse();
218        rhs.data.reverse();
219        let n = self.length() - rhs.length() + 1;
220        let mut res = self * rhs.inv(n);
221        res.truncate(n);
222        res.data.reverse();
223        res
224    }
225}
226impl<T, C> Rem for FormalPowerSeries<T, C>
227where
228    T: FormalPowerSeriesCoefficient,
229    C: ConvolveSteps<T = Vec<T>>,
230{
231    type Output = Self;
232    fn rem(self, rhs: Self) -> Self::Output {
233        let mut rem = self.clone() - self / rhs.clone() * rhs;
234        rem.trim_tail_zeros();
235        rem
236    }
237}
238
239impl<T, C> FormalPowerSeries<T, C>
240where
241    T: FormalPowerSeriesCoefficient,
242    C: ConvolveSteps<T = Vec<T>>,
243{
244    pub fn div_rem(self, rhs: Self) -> (Self, Self) {
245        let div = self.clone() / rhs.clone();
246        let mut rem = self - div.clone() * rhs;
247        rem.trim_tail_zeros();
248        (div, rem)
249    }
250}
251
252macro_rules! impl_fps_binop_conv {
253    ($imp:ident, $method:ident, $imp_assign:ident, $method_assign:ident) => {
254        impl<T, C> $imp_assign for FormalPowerSeries<T, C>
255        where
256            T: FormalPowerSeriesCoefficient,
257            C: ConvolveSteps<T = Vec<T>>,
258        {
259            fn $method_assign(&mut self, rhs: Self) {
260                *self = $imp::$method(Self::from_vec(take(&mut self.data)), rhs);
261            }
262        }
263        impl<T, C> $imp_assign<&Self> for FormalPowerSeries<T, C>
264        where
265            T: FormalPowerSeriesCoefficient,
266            C: ConvolveSteps<T = Vec<T>>,
267        {
268            fn $method_assign(&mut self, rhs: &Self) {
269                $imp_assign::$method_assign(self, rhs.clone());
270            }
271        }
272        impl<T, C> $imp<&FormalPowerSeries<T, C>> for FormalPowerSeries<T, C>
273        where
274            T: FormalPowerSeriesCoefficient,
275            C: ConvolveSteps<T = Vec<T>>,
276        {
277            type Output = Self;
278            fn $method(self, rhs: &FormalPowerSeries<T, C>) -> Self::Output {
279                $imp::$method(self, rhs.clone())
280            }
281        }
282        impl<T, C> $imp<FormalPowerSeries<T, C>> for &FormalPowerSeries<T, C>
283        where
284            T: FormalPowerSeriesCoefficient,
285            C: ConvolveSteps<T = Vec<T>>,
286        {
287            type Output = FormalPowerSeries<T, C>;
288            fn $method(self, rhs: FormalPowerSeries<T, C>) -> Self::Output {
289                $imp::$method(self.clone(), rhs)
290            }
291        }
292        impl<T, C> $imp<&FormalPowerSeries<T, C>> for &FormalPowerSeries<T, C>
293        where
294            T: FormalPowerSeriesCoefficient,
295            C: ConvolveSteps<T = Vec<T>>,
296        {
297            type Output = FormalPowerSeries<T, C>;
298            fn $method(self, rhs: &FormalPowerSeries<T, C>) -> Self::Output {
299                $imp::$method(self.clone(), rhs.clone())
300            }
301        }
302    };
303}
304impl_fps_binop_conv!(Mul, mul, MulAssign, mul_assign);
305impl_fps_binop_conv!(Div, div, DivAssign, div_assign);
306impl_fps_binop_conv!(Rem, rem, RemAssign, rem_assign);
307
308impl<T, C> Neg for FormalPowerSeries<T, C>
309where
310    T: FormalPowerSeriesCoefficient,
311{
312    type Output = Self;
313    fn neg(mut self) -> Self::Output {
314        for x in self.iter_mut() {
315            *x = -x.clone();
316        }
317        self
318    }
319}
320impl<T, C> Neg for &FormalPowerSeries<T, C>
321where
322    T: FormalPowerSeriesCoefficient,
323{
324    type Output = FormalPowerSeries<T, C>;
325    fn neg(self) -> Self::Output {
326        self.clone().neg()
327    }
328}
329
330impl<T, C> ShrAssign<usize> for FormalPowerSeries<T, C>
331where
332    T: FormalPowerSeriesCoefficient,
333{
334    fn shr_assign(&mut self, rhs: usize) {
335        if self.length() <= rhs {
336            *self = Self::zero();
337        } else {
338            for i in rhs..self.length() {
339                self[i - rhs] = self[i].clone();
340            }
341            self.truncate(self.length() - rhs);
342        }
343    }
344}
345impl<T, C> ShlAssign<usize> for FormalPowerSeries<T, C>
346where
347    T: FormalPowerSeriesCoefficient,
348{
349    fn shl_assign(&mut self, rhs: usize) {
350        let n = self.length();
351        self.resize(n + rhs);
352        for i in (0..n).rev() {
353            self[i + rhs] = self[i].clone();
354        }
355        for i in 0..rhs {
356            self[i] = T::zero();
357        }
358    }
359}
360
361impl<T, C> Shr<usize> for FormalPowerSeries<T, C>
362where
363    T: FormalPowerSeriesCoefficient,
364{
365    type Output = Self;
366    fn shr(mut self, rhs: usize) -> Self::Output {
367        self.shr_assign(rhs);
368        self
369    }
370}
371impl<T, C> Shl<usize> for FormalPowerSeries<T, C>
372where
373    T: FormalPowerSeriesCoefficient,
374{
375    type Output = Self;
376    fn shl(mut self, rhs: usize) -> Self::Output {
377        self.shl_assign(rhs);
378        self
379    }
380}
381impl<T, C> Shr<usize> for &FormalPowerSeries<T, C>
382where
383    T: FormalPowerSeriesCoefficient,
384{
385    type Output = FormalPowerSeries<T, C>;
386    fn shr(self, rhs: usize) -> Self::Output {
387        if self.length() <= rhs {
388            Self::Output::zero()
389        } else {
390            let mut f = Self::Output::zeros(self.length() - rhs);
391            for i in rhs..self.length() {
392                f[i - rhs] = self[i].clone();
393            }
394            f
395        }
396    }
397}
398impl<T, C> Shl<usize> for &FormalPowerSeries<T, C>
399where
400    T: FormalPowerSeriesCoefficient,
401{
402    type Output = FormalPowerSeries<T, C>;
403    fn shl(self, rhs: usize) -> Self::Output {
404        let mut f = Self::Output::zeros(self.length() + rhs);
405        for (i, x) in self.iter().cloned().enumerate().rev() {
406            f[i + rhs] = x;
407        }
408        f
409    }

More examples

Hide additional examples

crates/competitive/src/math/formal_power_series/formal_power_series_impls.rs (line 76)

75    pub fn trim_tail_zeros(&mut self) {
76        let mut len = self.length();
77        while len > 0 {
78            if self.data[len - 1].is_zero() {
79                len -= 1;
80            } else {
81                break;
82            }
83        }
84        self.truncate(len);
85    }
86}
87
88impl<T, C> Zero for FormalPowerSeries<T, C>
89where
90    T: PartialEq,
91{
92    fn zero() -> Self {
93        Self::from_vec(Vec::new())
94    }
95}
96impl<T, C> One for FormalPowerSeries<T, C>
97where
98    T: PartialEq + One,
99{
100    fn one() -> Self {
101        Self::from(T::one())
102    }
103}
104
105impl<T, C> IntoIterator for FormalPowerSeries<T, C> {
106    type Item = T;
107    type IntoIter = std::vec::IntoIter<T>;
108    fn into_iter(self) -> Self::IntoIter {
109        self.data.into_iter()
110    }
111}
112impl<'a, T, C> IntoIterator for &'a FormalPowerSeries<T, C> {
113    type Item = &'a T;
114    type IntoIter = Iter<'a, T>;
115    fn into_iter(self) -> Self::IntoIter {
116        self.data.iter()
117    }
118}
119impl<'a, T, C> IntoIterator for &'a mut FormalPowerSeries<T, C> {
120    type Item = &'a mut T;
121    type IntoIter = IterMut<'a, T>;
122    fn into_iter(self) -> Self::IntoIter {
123        self.data.iter_mut()
124    }
125}
126
127impl<T, C> FromIterator<T> for FormalPowerSeries<T, C> {
128    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
129        Self::from_vec(iter.into_iter().collect())
130    }
131}
132
133impl<T, C> Index<usize> for FormalPowerSeries<T, C> {
134    type Output = T;
135    fn index(&self, index: usize) -> &Self::Output {
136        &self.data[index]
137    }
138}
139impl<T, C> IndexMut<usize> for FormalPowerSeries<T, C> {
140    fn index_mut(&mut self, index: usize) -> &mut Self::Output {
141        &mut self.data[index]
142    }
143}
144
145impl<T, C> From<T> for FormalPowerSeries<T, C> {
146    fn from(x: T) -> Self {
147        once(x).collect()
148    }
149}
150impl<T, C> From<Vec<T>> for FormalPowerSeries<T, C> {
151    fn from(data: Vec<T>) -> Self {
152        Self::from_vec(data)
153    }
154}
155
156impl<T, C> FormalPowerSeries<T, C>
157where
158    T: FormalPowerSeriesCoefficient,
159{
160    pub fn prefix_ref(&self, deg: usize) -> Self {
161        if deg < self.length() {
162            Self::from_vec(self.data[..deg].to_vec())
163        } else {
164            self.clone()
165        }
166    }
167    pub fn prefix(mut self, deg: usize) -> Self {
168        self.data.truncate(deg);
169        self
170    }
171    pub fn even(mut self) -> Self {
172        let mut keep = false;
173        self.data.retain(|_| {
174            keep = !keep;
175            keep
176        });
177        self
178    }
179    pub fn odd(mut self) -> Self {
180        let mut keep = true;
181        self.data.retain(|_| {
182            keep = !keep;
183            keep
184        });
185        self
186    }
187    pub fn diff(mut self) -> Self {
188        let mut c = T::one();
189        for x in self.iter_mut().skip(1) {
190            *x *= &c;
191            c += T::one();
192        }
193        if self.length() > 0 {
194            self.data.remove(0);
195        }
196        self
197    }
198    pub fn integral(mut self) -> Self {
199        let n = self.length();
200        self.data.insert(0, Zero::zero());
201        let mut fact = Vec::with_capacity(n + 1);
202        let mut c = T::one();
203        fact.push(c.clone());
204        for _ in 1..n {
205            fact.push(fact.last().cloned().unwrap() * c.clone());
206            c += T::one();
207        }
208        let mut invf = T::one() / (fact.last().cloned().unwrap() * c.clone());
209        for x in self.iter_mut().skip(1).rev() {
210            *x *= invf.clone() * fact.pop().unwrap();
211            invf *= c.clone();
212            c -= T::one();
213        }
214        self
215    }
216    pub fn parity_inversion(mut self) -> Self {
217        self.iter_mut()
218            .skip(1)
219            .step_by(2)
220            .for_each(|x| *x = -x.clone());
221        self
222    }
223    pub fn eval(&self, x: T) -> T {
224        let mut base = T::one();
225        let mut res = T::zero();
226        for a in self.iter() {
227            res += base.clone() * a.clone();
228            base *= x.clone();
229        }
230        res
231    }
232}
233
234impl<T, C> FormalPowerSeries<T, C>
235where
236    T: FormalPowerSeriesCoefficient,
237    C: ConvolveSteps<T = Vec<T>>,
238{
239    pub fn inv(&self, deg: usize) -> Self {
240        debug_assert!(!self[0].is_zero());
241        let mut f = Self::from(T::one() / self[0].clone());
242        let mut i = 1;
243        while i < deg {
244            let g = self.prefix_ref((i * 2).min(deg));
245            let h = f.clone();
246            let mut g = C::transform(g.data, 2 * i);
247            let h = C::transform(h.data, 2 * i);
248            C::multiply(&mut g, &h);
249            let mut g = Self::from_vec(C::inverse_transform(g, 2 * i));
250            g >>= i;
251            let mut g = C::transform(g.data, 2 * i);
252            C::multiply(&mut g, &h);
253            let g = Self::from_vec(C::inverse_transform(g, 2 * i));
254            f.data.extend((-g).into_iter().take(i));
255            i *= 2;
256        }
257        f.truncate(deg);
258        f
259    }
260    pub fn exp(&self, deg: usize) -> Self {
261        debug_assert!(self[0].is_zero());
262        let mut f = Self::one();
263        let mut i = 1;
264        while i < deg {
265            let mut g = -f.log(i * 2);
266            g[0] += T::one();
267            for (g, x) in g.iter_mut().zip(self.iter().take(i * 2)) {
268                *g += x.clone();
269            }
270            f = (f * g).prefix(i * 2);
271            i *= 2;
272        }
273        f.prefix(deg)
274    }
275    pub fn log(&self, deg: usize) -> Self {
276        (self.inv(deg) * self.clone().diff()).integral().prefix(deg)
277    }
278    pub fn pow(&self, rhs: usize, deg: usize) -> Self {
279        if rhs == 0 {
280            return Self::from_vec(
281                once(T::one())
282                    .chain(repeat_with(T::zero))
283                    .take(deg)
284                    .collect(),
285            );
286        }
287        if let Some(k) = self.iter().position(|x| !x.is_zero()) {
288            if k >= (deg + rhs - 1) / rhs {
289                Self::zeros(deg)
290            } else {
291                let mut x0 = self[k].clone();
292                let rev = T::one() / x0.clone();
293                let x = {
294                    let mut x = T::one();
295                    let mut y = rhs;
296                    while y > 0 {
297                        if y & 1 == 1 {
298                            x *= x0.clone();
299                        }
300                        x0 *= x0.clone();
301                        y >>= 1;
302                    }
303                    x
304                };
305                let mut f = (self.clone() * &rev) >> k;
306                f = (f.log(deg) * &T::from(rhs)).exp(deg) * &x;
307                f.truncate(deg - k * rhs);
308                f <<= k * rhs;
309                f
310            }
311        } else {
312            Self::zeros(deg)
313        }
314    }
315}
316
317impl<T, C> FormalPowerSeries<T, C>
318where
319    T: FormalPowerSeriesCoefficientSqrt,
320    C: ConvolveSteps<T = Vec<T>>,
321{
322    pub fn sqrt(&self, deg: usize) -> Option<Self> {
323        if self[0].is_zero() {
324            if let Some(k) = self.iter().position(|x| !x.is_zero()) {
325                if k % 2 != 0 {
326                    return None;
327                } else if deg > k / 2 {
328                    return Some((self >> k).sqrt(deg - k / 2)? << (k / 2));
329                }
330            }
331        } else {
332            let inv2 = T::one() / (T::one() + T::one());
333            let mut f = Self::from(self[0].sqrt_coefficient()?);
334            let mut i = 1;
335            while i < deg {
336                f = (&f + &(self.prefix_ref(i * 2) * f.inv(i * 2))).prefix(i * 2) * &inv2;
337                i *= 2;
338            }
339            f.truncate(deg);
340            return Some(f);
341        }
342        Some(Self::zeros(deg))
343    }
344}
345
346impl<T, C> FormalPowerSeries<T, C>
347where
348    T: FormalPowerSeriesCoefficient,
349    C: ConvolveSteps<T = Vec<T>>,
350{
351    pub fn count_subset_sum<F>(&self, deg: usize, mut inverse: F) -> Self
352    where
353        F: FnMut(usize) -> T,
354    {
355        let n = self.length();
356        let mut f = Self::zeros(n);
357        for i in 1..n {
358            if !self[i].is_zero() {
359                for (j, d) in (0..n).step_by(i).enumerate().skip(1) {
360                    if j & 1 != 0 {
361                        f[d] += self[i].clone() * &inverse(j);
362                    } else {
363                        f[d] -= self[i].clone() * &inverse(j);
364                    }
365                }
366            }
367        }
368        f.exp(deg)
369    }
370    pub fn count_multiset_sum<F>(&self, deg: usize, mut inverse: F) -> Self
371    where
372        F: FnMut(usize) -> T,
373    {
374        let n = self.length();
375        let mut f = Self::zeros(n);
376        for i in 1..n {
377            if !self[i].is_zero() {
378                for (j, d) in (0..n).step_by(i).enumerate().skip(1) {
379                    f[d] += self[i].clone() * &inverse(j);
380                }
381            }
382        }
383        f.exp(deg)
384    }
385    /// [x^n] P(x) / Q(x)
386    pub fn bostan_mori(self, rhs: Self, mut n: usize) -> T {
387        let mut p = self;
388        let mut q = rhs;
389        while n > 0 {
390            let mq = q.clone().parity_inversion();
391            let u = p * mq.clone();
392            p = if n % 2 == 0 { u.even() } else { u.odd() };
393            q = (q * mq).even();
394            n /= 2;
395        }
396        p[0].clone() / q[0].clone()
397    }
398    /// return F(x) where [x^n] P(x) / Q(x) = [x^d-1] P(x) F(x)
399    pub fn bostan_mori_msb(self, n: usize) -> Self {
400        let d = self.length() - 1;
401        if n == 0 {
402            return (Self::one() << (d - 1)) / self[0].clone();
403        }
404        let q = self;
405        let mq = q.clone().parity_inversion();
406        let w = (q * &mq).even().bostan_mori_msb(n / 2);
407        let mut s = Self::zeros(w.length() * 2 - (n % 2));
408        for (i, x) in w.iter().enumerate() {
409            s[i * 2 + (1 - n % 2)] = x.clone();
410        }
411        let len = 2 * d + 1;
412        let ts = C::transform(s.prefix(len).data, len);
413        mq.reversed().middle_product(&ts, len).prefix(d + 1)
414    }
415    /// x^n mod self
416    pub fn pow_mod(self, n: usize) -> Self {
417        let d = self.length() - 1;
418        let q = self.reversed();
419        let u = q.clone().bostan_mori_msb(n);
420        let mut f = (u * q).prefix(d).reversed();
421        f.trim_tail_zeros();
422        f
423    }
424    fn middle_product(self, other: &C::F, deg: usize) -> Self {
425        let n = self.length();
426        let mut s = C::transform(self.reversed().data, deg);
427        C::multiply(&mut s, other);
428        Self::from_vec((C::inverse_transform(s, deg))[n - 1..].to_vec())
429    }
430    pub fn multipoint_evaluation(self, points: &[T]) -> Vec<T> {
431        let n = points.len();
432        if n <= 32 {
433            return points.iter().map(|p| self.eval(p.clone())).collect();
434        }
435        let mut subproduct_tree = Vec::with_capacity(n * 2);
436        subproduct_tree.resize_with(n, Zero::zero);
437        for x in points {
438            subproduct_tree.push(Self::from_vec(vec![-x.clone(), T::one()]));
439        }
440        for i in (1..n).rev() {
441            subproduct_tree[i] = &subproduct_tree[i * 2] * &subproduct_tree[i * 2 + 1];
442        }
443        let mut uptree_t = Vec::with_capacity(n * 2);
444        uptree_t.resize_with(1, Zero::zero);
445        subproduct_tree.reverse();
446        subproduct_tree.pop();
447        let m = self.length();
448        let v = subproduct_tree.pop().unwrap().reversed().resized(m);
449        let s = C::transform(self.data, m * 2);
450        uptree_t.push(v.inv(m).middle_product(&s, m * 2).resized(n).reversed());
451        for i in 1..n {
452            let subl = subproduct_tree.pop().unwrap();
453            let subr = subproduct_tree.pop().unwrap();
454            let (dl, dr) = (subl.length(), subr.length());
455            let len = dl.max(dr) + uptree_t[i].length();
456            let s = C::transform(uptree_t[i].data.to_vec(), len);
457            uptree_t.push(subr.middle_product(&s, len).prefix(dl));
458            uptree_t.push(subl.middle_product(&s, len).prefix(dr));
459        }
460        uptree_t[n..]
461            .iter()
462            .map(|u| u.data.first().cloned().unwrap_or_else(Zero::zero))
463            .collect()
464    }
465    pub fn product_all<I>(iter: I, deg: usize) -> Self
466    where
467        I: IntoIterator<Item = Self>,
468    {
469        let mut heap: BinaryHeap<_> = iter
470            .into_iter()
471            .map(|f| PartialIgnoredOrd(Reverse(f.length()), f))
472            .collect();
473        while let Some(PartialIgnoredOrd(_, x)) = heap.pop() {
474            if let Some(PartialIgnoredOrd(_, y)) = heap.pop() {
475                let z = (x * y).prefix(deg);
476                heap.push(PartialIgnoredOrd(Reverse(z.length()), z));
477            } else {
478                return x;
479            }
480        }
481        Self::one()
482    }
483    pub fn sum_all_rational<I>(iter: I, deg: usize) -> (Self, Self)
484    where
485        I: IntoIterator<Item = (Self, Self)>,
486    {
487        let mut heap: BinaryHeap<_> = iter
488            .into_iter()
489            .map(|(f, g)| PartialIgnoredOrd(Reverse(f.length().max(g.length())), (f, g)))
490            .collect();
491        while let Some(PartialIgnoredOrd(_, (xa, xb))) = heap.pop() {
492            if let Some(PartialIgnoredOrd(_, (ya, yb))) = heap.pop() {
493                let zb = (&xb * &yb).prefix(deg);
494                let za = (xa * yb + ya * xb).prefix(deg);
495                heap.push(PartialIgnoredOrd(
496                    Reverse(za.length().max(zb.length())),
497                    (za, zb),
498                ));
499            } else {
500                return (xa, xb);
501            }
502        }
503        (Self::zero(), Self::one())
504    }
505    pub fn kth_term_of_linearly_recurrence(self, a: Vec<T>, k: usize) -> T {
506        if let Some(x) = a.get(k) {
507            return x.clone();
508        }
509        let p = (Self::from_vec(a).prefix(self.length() - 1) * &self).prefix(self.length() - 1);
510        p.bostan_mori(self, k)
511    }
512    pub fn kth_term(a: Vec<T>, k: usize) -> T {
513        if let Some(x) = a.get(k) {
514            return x.clone();
515        }
516        Self::from_vec(berlekamp_massey(&a)).kth_term_of_linearly_recurrence(a, k)
517    }
518    /// sum_i a_i exp(b_i x)
519    pub fn linear_sum_of_exp<I, F>(iter: I, deg: usize, mut inv_fact: F) -> Self
520    where
521        I: IntoIterator<Item = (T, T)>,
522        F: FnMut(usize) -> T,
523    {
524        let (p, q) = Self::sum_all_rational(
525            iter.into_iter()
526                .map(|(a, b)| (Self::from_vec(vec![a]), Self::from_vec(vec![T::one(), -b]))),
527            deg,
528        );
529        let mut f = (p * q.inv(deg)).prefix(deg);
530        for i in 0..f.length() {
531            f[i] *= inv_fact(i);
532        }
533        f
534    }
535}
536
537impl<M, C> FormalPowerSeries<MInt<M>, C>
538where
539    M: MIntConvert<usize>,
540    C: ConvolveSteps<T = Vec<MInt<M>>>,
541{
542    /// f(x) <- f(x + a)
543    pub fn taylor_shift(mut self, a: MInt<M>, f: &MemorizedFactorial<M>) -> Self {
544        let n = self.length();
545        for i in 0..n {
546            self.data[i] *= f.fact[i];
547        }
548        self.data.reverse();
549        let mut b = a;
550        let mut g = Self::from_vec(f.inv_fact[..n].to_vec());
551        for i in 1..n {
552            g[i] *= b;
553            b *= a;
554        }
555        self *= g;
556        self.truncate(n);
557        self.data.reverse();
558        for i in 0..n {
559            self.data[i] *= f.inv_fact[i];
560        }
561        self
562    }

Source

pub fn truncate(&mut self, deg: usize)

Examples found in repository ?

crates/competitive/src/math/formal_power_series/formal_power_series_impls.rs (line 84)

75    pub fn trim_tail_zeros(&mut self) {
76        let mut len = self.length();
77        while len > 0 {
78            if self.data[len - 1].is_zero() {
79                len -= 1;
80            } else {
81                break;
82            }
83        }
84        self.truncate(len);
85    }
86}
87
88impl<T, C> Zero for FormalPowerSeries<T, C>
89where
90    T: PartialEq,
91{
92    fn zero() -> Self {
93        Self::from_vec(Vec::new())
94    }
95}
96impl<T, C> One for FormalPowerSeries<T, C>
97where
98    T: PartialEq + One,
99{
100    fn one() -> Self {
101        Self::from(T::one())
102    }
103}
104
105impl<T, C> IntoIterator for FormalPowerSeries<T, C> {
106    type Item = T;
107    type IntoIter = std::vec::IntoIter<T>;
108    fn into_iter(self) -> Self::IntoIter {
109        self.data.into_iter()
110    }
111}
112impl<'a, T, C> IntoIterator for &'a FormalPowerSeries<T, C> {
113    type Item = &'a T;
114    type IntoIter = Iter<'a, T>;
115    fn into_iter(self) -> Self::IntoIter {
116        self.data.iter()
117    }
118}
119impl<'a, T, C> IntoIterator for &'a mut FormalPowerSeries<T, C> {
120    type Item = &'a mut T;
121    type IntoIter = IterMut<'a, T>;
122    fn into_iter(self) -> Self::IntoIter {
123        self.data.iter_mut()
124    }
125}
126
127impl<T, C> FromIterator<T> for FormalPowerSeries<T, C> {
128    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
129        Self::from_vec(iter.into_iter().collect())
130    }
131}
132
133impl<T, C> Index<usize> for FormalPowerSeries<T, C> {
134    type Output = T;
135    fn index(&self, index: usize) -> &Self::Output {
136        &self.data[index]
137    }
138}
139impl<T, C> IndexMut<usize> for FormalPowerSeries<T, C> {
140    fn index_mut(&mut self, index: usize) -> &mut Self::Output {
141        &mut self.data[index]
142    }
143}
144
145impl<T, C> From<T> for FormalPowerSeries<T, C> {
146    fn from(x: T) -> Self {
147        once(x).collect()
148    }
149}
150impl<T, C> From<Vec<T>> for FormalPowerSeries<T, C> {
151    fn from(data: Vec<T>) -> Self {
152        Self::from_vec(data)
153    }
154}
155
156impl<T, C> FormalPowerSeries<T, C>
157where
158    T: FormalPowerSeriesCoefficient,
159{
160    pub fn prefix_ref(&self, deg: usize) -> Self {
161        if deg < self.length() {
162            Self::from_vec(self.data[..deg].to_vec())
163        } else {
164            self.clone()
165        }
166    }
167    pub fn prefix(mut self, deg: usize) -> Self {
168        self.data.truncate(deg);
169        self
170    }
171    pub fn even(mut self) -> Self {
172        let mut keep = false;
173        self.data.retain(|_| {
174            keep = !keep;
175            keep
176        });
177        self
178    }
179    pub fn odd(mut self) -> Self {
180        let mut keep = true;
181        self.data.retain(|_| {
182            keep = !keep;
183            keep
184        });
185        self
186    }
187    pub fn diff(mut self) -> Self {
188        let mut c = T::one();
189        for x in self.iter_mut().skip(1) {
190            *x *= &c;
191            c += T::one();
192        }
193        if self.length() > 0 {
194            self.data.remove(0);
195        }
196        self
197    }
198    pub fn integral(mut self) -> Self {
199        let n = self.length();
200        self.data.insert(0, Zero::zero());
201        let mut fact = Vec::with_capacity(n + 1);
202        let mut c = T::one();
203        fact.push(c.clone());
204        for _ in 1..n {
205            fact.push(fact.last().cloned().unwrap() * c.clone());
206            c += T::one();
207        }
208        let mut invf = T::one() / (fact.last().cloned().unwrap() * c.clone());
209        for x in self.iter_mut().skip(1).rev() {
210            *x *= invf.clone() * fact.pop().unwrap();
211            invf *= c.clone();
212            c -= T::one();
213        }
214        self
215    }
216    pub fn parity_inversion(mut self) -> Self {
217        self.iter_mut()
218            .skip(1)
219            .step_by(2)
220            .for_each(|x| *x = -x.clone());
221        self
222    }
223    pub fn eval(&self, x: T) -> T {
224        let mut base = T::one();
225        let mut res = T::zero();
226        for a in self.iter() {
227            res += base.clone() * a.clone();
228            base *= x.clone();
229        }
230        res
231    }
232}
233
234impl<T, C> FormalPowerSeries<T, C>
235where
236    T: FormalPowerSeriesCoefficient,
237    C: ConvolveSteps<T = Vec<T>>,
238{
239    pub fn inv(&self, deg: usize) -> Self {
240        debug_assert!(!self[0].is_zero());
241        let mut f = Self::from(T::one() / self[0].clone());
242        let mut i = 1;
243        while i < deg {
244            let g = self.prefix_ref((i * 2).min(deg));
245            let h = f.clone();
246            let mut g = C::transform(g.data, 2 * i);
247            let h = C::transform(h.data, 2 * i);
248            C::multiply(&mut g, &h);
249            let mut g = Self::from_vec(C::inverse_transform(g, 2 * i));
250            g >>= i;
251            let mut g = C::transform(g.data, 2 * i);
252            C::multiply(&mut g, &h);
253            let g = Self::from_vec(C::inverse_transform(g, 2 * i));
254            f.data.extend((-g).into_iter().take(i));
255            i *= 2;
256        }
257        f.truncate(deg);
258        f
259    }
260    pub fn exp(&self, deg: usize) -> Self {
261        debug_assert!(self[0].is_zero());
262        let mut f = Self::one();
263        let mut i = 1;
264        while i < deg {
265            let mut g = -f.log(i * 2);
266            g[0] += T::one();
267            for (g, x) in g.iter_mut().zip(self.iter().take(i * 2)) {
268                *g += x.clone();
269            }
270            f = (f * g).prefix(i * 2);
271            i *= 2;
272        }
273        f.prefix(deg)
274    }
275    pub fn log(&self, deg: usize) -> Self {
276        (self.inv(deg) * self.clone().diff()).integral().prefix(deg)
277    }
278    pub fn pow(&self, rhs: usize, deg: usize) -> Self {
279        if rhs == 0 {
280            return Self::from_vec(
281                once(T::one())
282                    .chain(repeat_with(T::zero))
283                    .take(deg)
284                    .collect(),
285            );
286        }
287        if let Some(k) = self.iter().position(|x| !x.is_zero()) {
288            if k >= (deg + rhs - 1) / rhs {
289                Self::zeros(deg)
290            } else {
291                let mut x0 = self[k].clone();
292                let rev = T::one() / x0.clone();
293                let x = {
294                    let mut x = T::one();
295                    let mut y = rhs;
296                    while y > 0 {
297                        if y & 1 == 1 {
298                            x *= x0.clone();
299                        }
300                        x0 *= x0.clone();
301                        y >>= 1;
302                    }
303                    x
304                };
305                let mut f = (self.clone() * &rev) >> k;
306                f = (f.log(deg) * &T::from(rhs)).exp(deg) * &x;
307                f.truncate(deg - k * rhs);
308                f <<= k * rhs;
309                f
310            }
311        } else {
312            Self::zeros(deg)
313        }
314    }
315}
316
317impl<T, C> FormalPowerSeries<T, C>
318where
319    T: FormalPowerSeriesCoefficientSqrt,
320    C: ConvolveSteps<T = Vec<T>>,
321{
322    pub fn sqrt(&self, deg: usize) -> Option<Self> {
323        if self[0].is_zero() {
324            if let Some(k) = self.iter().position(|x| !x.is_zero()) {
325                if k % 2 != 0 {
326                    return None;
327                } else if deg > k / 2 {
328                    return Some((self >> k).sqrt(deg - k / 2)? << (k / 2));
329                }
330            }
331        } else {
332            let inv2 = T::one() / (T::one() + T::one());
333            let mut f = Self::from(self[0].sqrt_coefficient()?);
334            let mut i = 1;
335            while i < deg {
336                f = (&f + &(self.prefix_ref(i * 2) * f.inv(i * 2))).prefix(i * 2) * &inv2;
337                i *= 2;
338            }
339            f.truncate(deg);
340            return Some(f);
341        }
342        Some(Self::zeros(deg))
343    }
344}
345
346impl<T, C> FormalPowerSeries<T, C>
347where
348    T: FormalPowerSeriesCoefficient,
349    C: ConvolveSteps<T = Vec<T>>,
350{
351    pub fn count_subset_sum<F>(&self, deg: usize, mut inverse: F) -> Self
352    where
353        F: FnMut(usize) -> T,
354    {
355        let n = self.length();
356        let mut f = Self::zeros(n);
357        for i in 1..n {
358            if !self[i].is_zero() {
359                for (j, d) in (0..n).step_by(i).enumerate().skip(1) {
360                    if j & 1 != 0 {
361                        f[d] += self[i].clone() * &inverse(j);
362                    } else {
363                        f[d] -= self[i].clone() * &inverse(j);
364                    }
365                }
366            }
367        }
368        f.exp(deg)
369    }
370    pub fn count_multiset_sum<F>(&self, deg: usize, mut inverse: F) -> Self
371    where
372        F: FnMut(usize) -> T,
373    {
374        let n = self.length();
375        let mut f = Self::zeros(n);
376        for i in 1..n {
377            if !self[i].is_zero() {
378                for (j, d) in (0..n).step_by(i).enumerate().skip(1) {
379                    f[d] += self[i].clone() * &inverse(j);
380                }
381            }
382        }
383        f.exp(deg)
384    }
385    /// [x^n] P(x) / Q(x)
386    pub fn bostan_mori(self, rhs: Self, mut n: usize) -> T {
387        let mut p = self;
388        let mut q = rhs;
389        while n > 0 {
390            let mq = q.clone().parity_inversion();
391            let u = p * mq.clone();
392            p = if n % 2 == 0 { u.even() } else { u.odd() };
393            q = (q * mq).even();
394            n /= 2;
395        }
396        p[0].clone() / q[0].clone()
397    }
398    /// return F(x) where [x^n] P(x) / Q(x) = [x^d-1] P(x) F(x)
399    pub fn bostan_mori_msb(self, n: usize) -> Self {
400        let d = self.length() - 1;
401        if n == 0 {
402            return (Self::one() << (d - 1)) / self[0].clone();
403        }
404        let q = self;
405        let mq = q.clone().parity_inversion();
406        let w = (q * &mq).even().bostan_mori_msb(n / 2);
407        let mut s = Self::zeros(w.length() * 2 - (n % 2));
408        for (i, x) in w.iter().enumerate() {
409            s[i * 2 + (1 - n % 2)] = x.clone();
410        }
411        let len = 2 * d + 1;
412        let ts = C::transform(s.prefix(len).data, len);
413        mq.reversed().middle_product(&ts, len).prefix(d + 1)
414    }
415    /// x^n mod self
416    pub fn pow_mod(self, n: usize) -> Self {
417        let d = self.length() - 1;
418        let q = self.reversed();
419        let u = q.clone().bostan_mori_msb(n);
420        let mut f = (u * q).prefix(d).reversed();
421        f.trim_tail_zeros();
422        f
423    }
424    fn middle_product(self, other: &C::F, deg: usize) -> Self {
425        let n = self.length();
426        let mut s = C::transform(self.reversed().data, deg);
427        C::multiply(&mut s, other);
428        Self::from_vec((C::inverse_transform(s, deg))[n - 1..].to_vec())
429    }
430    pub fn multipoint_evaluation(self, points: &[T]) -> Vec<T> {
431        let n = points.len();
432        if n <= 32 {
433            return points.iter().map(|p| self.eval(p.clone())).collect();
434        }
435        let mut subproduct_tree = Vec::with_capacity(n * 2);
436        subproduct_tree.resize_with(n, Zero::zero);
437        for x in points {
438            subproduct_tree.push(Self::from_vec(vec![-x.clone(), T::one()]));
439        }
440        for i in (1..n).rev() {
441            subproduct_tree[i] = &subproduct_tree[i * 2] * &subproduct_tree[i * 2 + 1];
442        }
443        let mut uptree_t = Vec::with_capacity(n * 2);
444        uptree_t.resize_with(1, Zero::zero);
445        subproduct_tree.reverse();
446        subproduct_tree.pop();
447        let m = self.length();
448        let v = subproduct_tree.pop().unwrap().reversed().resized(m);
449        let s = C::transform(self.data, m * 2);
450        uptree_t.push(v.inv(m).middle_product(&s, m * 2).resized(n).reversed());
451        for i in 1..n {
452            let subl = subproduct_tree.pop().unwrap();
453            let subr = subproduct_tree.pop().unwrap();
454            let (dl, dr) = (subl.length(), subr.length());
455            let len = dl.max(dr) + uptree_t[i].length();
456            let s = C::transform(uptree_t[i].data.to_vec(), len);
457            uptree_t.push(subr.middle_product(&s, len).prefix(dl));
458            uptree_t.push(subl.middle_product(&s, len).prefix(dr));
459        }
460        uptree_t[n..]
461            .iter()
462            .map(|u| u.data.first().cloned().unwrap_or_else(Zero::zero))
463            .collect()
464    }
465    pub fn product_all<I>(iter: I, deg: usize) -> Self
466    where
467        I: IntoIterator<Item = Self>,
468    {
469        let mut heap: BinaryHeap<_> = iter
470            .into_iter()
471            .map(|f| PartialIgnoredOrd(Reverse(f.length()), f))
472            .collect();
473        while let Some(PartialIgnoredOrd(_, x)) = heap.pop() {
474            if let Some(PartialIgnoredOrd(_, y)) = heap.pop() {
475                let z = (x * y).prefix(deg);
476                heap.push(PartialIgnoredOrd(Reverse(z.length()), z));
477            } else {
478                return x;
479            }
480        }
481        Self::one()
482    }
483    pub fn sum_all_rational<I>(iter: I, deg: usize) -> (Self, Self)
484    where
485        I: IntoIterator<Item = (Self, Self)>,
486    {
487        let mut heap: BinaryHeap<_> = iter
488            .into_iter()
489            .map(|(f, g)| PartialIgnoredOrd(Reverse(f.length().max(g.length())), (f, g)))
490            .collect();
491        while let Some(PartialIgnoredOrd(_, (xa, xb))) = heap.pop() {
492            if let Some(PartialIgnoredOrd(_, (ya, yb))) = heap.pop() {
493                let zb = (&xb * &yb).prefix(deg);
494                let za = (xa * yb + ya * xb).prefix(deg);
495                heap.push(PartialIgnoredOrd(
496                    Reverse(za.length().max(zb.length())),
497                    (za, zb),
498                ));
499            } else {
500                return (xa, xb);
501            }
502        }
503        (Self::zero(), Self::one())
504    }
505    pub fn kth_term_of_linearly_recurrence(self, a: Vec<T>, k: usize) -> T {
506        if let Some(x) = a.get(k) {
507            return x.clone();
508        }
509        let p = (Self::from_vec(a).prefix(self.length() - 1) * &self).prefix(self.length() - 1);
510        p.bostan_mori(self, k)
511    }
512    pub fn kth_term(a: Vec<T>, k: usize) -> T {
513        if let Some(x) = a.get(k) {
514            return x.clone();
515        }
516        Self::from_vec(berlekamp_massey(&a)).kth_term_of_linearly_recurrence(a, k)
517    }
518    /// sum_i a_i exp(b_i x)
519    pub fn linear_sum_of_exp<I, F>(iter: I, deg: usize, mut inv_fact: F) -> Self
520    where
521        I: IntoIterator<Item = (T, T)>,
522        F: FnMut(usize) -> T,
523    {
524        let (p, q) = Self::sum_all_rational(
525            iter.into_iter()
526                .map(|(a, b)| (Self::from_vec(vec![a]), Self::from_vec(vec![T::one(), -b]))),
527            deg,
528        );
529        let mut f = (p * q.inv(deg)).prefix(deg);
530        for i in 0..f.length() {
531            f[i] *= inv_fact(i);
532        }
533        f
534    }
535}
536
537impl<M, C> FormalPowerSeries<MInt<M>, C>
538where
539    M: MIntConvert<usize>,
540    C: ConvolveSteps<T = Vec<MInt<M>>>,
541{
542    /// f(x) <- f(x + a)
543    pub fn taylor_shift(mut self, a: MInt<M>, f: &MemorizedFactorial<M>) -> Self {
544        let n = self.length();
545        for i in 0..n {
546            self.data[i] *= f.fact[i];
547        }
548        self.data.reverse();
549        let mut b = a;
550        let mut g = Self::from_vec(f.inv_fact[..n].to_vec());
551        for i in 1..n {
552            g[i] *= b;
553            b *= a;
554        }
555        self *= g;
556        self.truncate(n);
557        self.data.reverse();
558        for i in 0..n {
559            self.data[i] *= f.inv_fact[i];
560        }
561        self
562    }

More examples

Hide additional examples

crates/competitive/src/math/formal_power_series/formal_power_series_nums.rs (line 221)

211    fn div(mut self, mut rhs: Self) -> Self::Output {
212        self.trim_tail_zeros();
213        rhs.trim_tail_zeros();
214        if self.length() < rhs.length() {
215            return Self::zero();
216        }
217        self.data.reverse();
218        rhs.data.reverse();
219        let n = self.length() - rhs.length() + 1;
220        let mut res = self * rhs.inv(n);
221        res.truncate(n);
222        res.data.reverse();
223        res
224    }
225}
226impl<T, C> Rem for FormalPowerSeries<T, C>
227where
228    T: FormalPowerSeriesCoefficient,
229    C: ConvolveSteps<T = Vec<T>>,
230{
231    type Output = Self;
232    fn rem(self, rhs: Self) -> Self::Output {
233        let mut rem = self.clone() - self / rhs.clone() * rhs;
234        rem.trim_tail_zeros();
235        rem
236    }
237}
238
239impl<T, C> FormalPowerSeries<T, C>
240where
241    T: FormalPowerSeriesCoefficient,
242    C: ConvolveSteps<T = Vec<T>>,
243{
244    pub fn div_rem(self, rhs: Self) -> (Self, Self) {
245        let div = self.clone() / rhs.clone();
246        let mut rem = self - div.clone() * rhs;
247        rem.trim_tail_zeros();
248        (div, rem)
249    }
250}
251
252macro_rules! impl_fps_binop_conv {
253    ($imp:ident, $method:ident, $imp_assign:ident, $method_assign:ident) => {
254        impl<T, C> $imp_assign for FormalPowerSeries<T, C>
255        where
256            T: FormalPowerSeriesCoefficient,
257            C: ConvolveSteps<T = Vec<T>>,
258        {
259            fn $method_assign(&mut self, rhs: Self) {
260                *self = $imp::$method(Self::from_vec(take(&mut self.data)), rhs);
261            }
262        }
263        impl<T, C> $imp_assign<&Self> for FormalPowerSeries<T, C>
264        where
265            T: FormalPowerSeriesCoefficient,
266            C: ConvolveSteps<T = Vec<T>>,
267        {
268            fn $method_assign(&mut self, rhs: &Self) {
269                $imp_assign::$method_assign(self, rhs.clone());
270            }
271        }
272        impl<T, C> $imp<&FormalPowerSeries<T, C>> for FormalPowerSeries<T, C>
273        where
274            T: FormalPowerSeriesCoefficient,
275            C: ConvolveSteps<T = Vec<T>>,
276        {
277            type Output = Self;
278            fn $method(self, rhs: &FormalPowerSeries<T, C>) -> Self::Output {
279                $imp::$method(self, rhs.clone())
280            }
281        }
282        impl<T, C> $imp<FormalPowerSeries<T, C>> for &FormalPowerSeries<T, C>
283        where
284            T: FormalPowerSeriesCoefficient,
285            C: ConvolveSteps<T = Vec<T>>,
286        {
287            type Output = FormalPowerSeries<T, C>;
288            fn $method(self, rhs: FormalPowerSeries<T, C>) -> Self::Output {
289                $imp::$method(self.clone(), rhs)
290            }
291        }
292        impl<T, C> $imp<&FormalPowerSeries<T, C>> for &FormalPowerSeries<T, C>
293        where
294            T: FormalPowerSeriesCoefficient,
295            C: ConvolveSteps<T = Vec<T>>,
296        {
297            type Output = FormalPowerSeries<T, C>;
298            fn $method(self, rhs: &FormalPowerSeries<T, C>) -> Self::Output {
299                $imp::$method(self.clone(), rhs.clone())
300            }
301        }
302    };
303}
304impl_fps_binop_conv!(Mul, mul, MulAssign, mul_assign);
305impl_fps_binop_conv!(Div, div, DivAssign, div_assign);
306impl_fps_binop_conv!(Rem, rem, RemAssign, rem_assign);
307
308impl<T, C> Neg for FormalPowerSeries<T, C>
309where
310    T: FormalPowerSeriesCoefficient,
311{
312    type Output = Self;
313    fn neg(mut self) -> Self::Output {
314        for x in self.iter_mut() {
315            *x = -x.clone();
316        }
317        self
318    }
319}
320impl<T, C> Neg for &FormalPowerSeries<T, C>
321where
322    T: FormalPowerSeriesCoefficient,
323{
324    type Output = FormalPowerSeries<T, C>;
325    fn neg(self) -> Self::Output {
326        self.clone().neg()
327    }
328}
329
330impl<T, C> ShrAssign<usize> for FormalPowerSeries<T, C>
331where
332    T: FormalPowerSeriesCoefficient,
333{
334    fn shr_assign(&mut self, rhs: usize) {
335        if self.length() <= rhs {
336            *self = Self::zero();
337        } else {
338            for i in rhs..self.length() {
339                self[i - rhs] = self[i].clone();
340            }
341            self.truncate(self.length() - rhs);
342        }
343    }

Source

pub fn iter(&self) -> Iter<'_, T>

Examples found in repository ?

crates/competitive/src/math/formal_power_series/formal_power_series_nums.rs (line 119)

115    fn add_assign(&mut self, rhs: &Self) {
116        if self.length() < rhs.length() {
117            self.resize(rhs.length());
118        }
119        for (x, y) in self.iter_mut().zip(rhs.iter()) {
120            x.add_assign(y);
121        }
122    }
123}
124impl<T, C> SubAssign<&Self> for FormalPowerSeries<T, C>
125where
126    T: FormalPowerSeriesCoefficient,
127{
128    fn sub_assign(&mut self, rhs: &Self) {
129        if self.length() < rhs.length() {
130            self.resize(rhs.length());
131        }
132        for (x, y) in self.iter_mut().zip(rhs.iter()) {
133            x.sub_assign(y);
134        }
135        self.trim_tail_zeros();
136    }
137}
138
139macro_rules! impl_fps_binop_addsub {
140    ($imp:ident, $method:ident, $imp_assign:ident, $method_assign:ident) => {
141        impl<T, C> $imp_assign for FormalPowerSeries<T, C>
142        where
143            T: FormalPowerSeriesCoefficient,
144        {
145            fn $method_assign(&mut self, rhs: Self) {
146                $imp_assign::$method_assign(self, &rhs);
147            }
148        }
149        impl<T, C> $imp for FormalPowerSeries<T, C>
150        where
151            T: FormalPowerSeriesCoefficient,
152        {
153            type Output = Self;
154            fn $method(mut self, rhs: Self) -> Self::Output {
155                $imp_assign::$method_assign(&mut self, &rhs);
156                self
157            }
158        }
159        impl<T, C> $imp<&FormalPowerSeries<T, C>> for FormalPowerSeries<T, C>
160        where
161            T: FormalPowerSeriesCoefficient,
162        {
163            type Output = Self;
164            fn $method(mut self, rhs: &FormalPowerSeries<T, C>) -> Self::Output {
165                $imp_assign::$method_assign(&mut self, rhs);
166                self
167            }
168        }
169        impl<T, C> $imp<FormalPowerSeries<T, C>> for &FormalPowerSeries<T, C>
170        where
171            T: FormalPowerSeriesCoefficient,
172        {
173            type Output = FormalPowerSeries<T, C>;
174            fn $method(self, rhs: FormalPowerSeries<T, C>) -> Self::Output {
175                let mut self_ = self.clone();
176                $imp_assign::$method_assign(&mut self_, &rhs);
177                self_
178            }
179        }
180        impl<T, C> $imp<&FormalPowerSeries<T, C>> for &FormalPowerSeries<T, C>
181        where
182            T: FormalPowerSeriesCoefficient,
183        {
184            type Output = FormalPowerSeries<T, C>;
185            fn $method(self, rhs: &FormalPowerSeries<T, C>) -> Self::Output {
186                let mut self_ = self.clone();
187                $imp_assign::$method_assign(&mut self_, rhs);
188                self_
189            }
190        }
191    };
192}
193impl_fps_binop_addsub!(Add, add, AddAssign, add_assign);
194impl_fps_binop_addsub!(Sub, sub, SubAssign, sub_assign);
195
196impl<T, C> Mul for FormalPowerSeries<T, C>
197where
198    C: ConvolveSteps<T = Vec<T>>,
199{
200    type Output = Self;
201    fn mul(self, rhs: Self) -> Self::Output {
202        Self::from_vec(C::convolve(self.data, rhs.data))
203    }
204}
205impl<T, C> Div for FormalPowerSeries<T, C>
206where
207    T: FormalPowerSeriesCoefficient,
208    C: ConvolveSteps<T = Vec<T>>,
209{
210    type Output = Self;
211    fn div(mut self, mut rhs: Self) -> Self::Output {
212        self.trim_tail_zeros();
213        rhs.trim_tail_zeros();
214        if self.length() < rhs.length() {
215            return Self::zero();
216        }
217        self.data.reverse();
218        rhs.data.reverse();
219        let n = self.length() - rhs.length() + 1;
220        let mut res = self * rhs.inv(n);
221        res.truncate(n);
222        res.data.reverse();
223        res
224    }
225}
226impl<T, C> Rem for FormalPowerSeries<T, C>
227where
228    T: FormalPowerSeriesCoefficient,
229    C: ConvolveSteps<T = Vec<T>>,
230{
231    type Output = Self;
232    fn rem(self, rhs: Self) -> Self::Output {
233        let mut rem = self.clone() - self / rhs.clone() * rhs;
234        rem.trim_tail_zeros();
235        rem
236    }
237}
238
239impl<T, C> FormalPowerSeries<T, C>
240where
241    T: FormalPowerSeriesCoefficient,
242    C: ConvolveSteps<T = Vec<T>>,
243{
244    pub fn div_rem(self, rhs: Self) -> (Self, Self) {
245        let div = self.clone() / rhs.clone();
246        let mut rem = self - div.clone() * rhs;
247        rem.trim_tail_zeros();
248        (div, rem)
249    }
250}
251
252macro_rules! impl_fps_binop_conv {
253    ($imp:ident, $method:ident, $imp_assign:ident, $method_assign:ident) => {
254        impl<T, C> $imp_assign for FormalPowerSeries<T, C>
255        where
256            T: FormalPowerSeriesCoefficient,
257            C: ConvolveSteps<T = Vec<T>>,
258        {
259            fn $method_assign(&mut self, rhs: Self) {
260                *self = $imp::$method(Self::from_vec(take(&mut self.data)), rhs);
261            }
262        }
263        impl<T, C> $imp_assign<&Self> for FormalPowerSeries<T, C>
264        where
265            T: FormalPowerSeriesCoefficient,
266            C: ConvolveSteps<T = Vec<T>>,
267        {
268            fn $method_assign(&mut self, rhs: &Self) {
269                $imp_assign::$method_assign(self, rhs.clone());
270            }
271        }
272        impl<T, C> $imp<&FormalPowerSeries<T, C>> for FormalPowerSeries<T, C>
273        where
274            T: FormalPowerSeriesCoefficient,
275            C: ConvolveSteps<T = Vec<T>>,
276        {
277            type Output = Self;
278            fn $method(self, rhs: &FormalPowerSeries<T, C>) -> Self::Output {
279                $imp::$method(self, rhs.clone())
280            }
281        }
282        impl<T, C> $imp<FormalPowerSeries<T, C>> for &FormalPowerSeries<T, C>
283        where
284            T: FormalPowerSeriesCoefficient,
285            C: ConvolveSteps<T = Vec<T>>,
286        {
287            type Output = FormalPowerSeries<T, C>;
288            fn $method(self, rhs: FormalPowerSeries<T, C>) -> Self::Output {
289                $imp::$method(self.clone(), rhs)
290            }
291        }
292        impl<T, C> $imp<&FormalPowerSeries<T, C>> for &FormalPowerSeries<T, C>
293        where
294            T: FormalPowerSeriesCoefficient,
295            C: ConvolveSteps<T = Vec<T>>,
296        {
297            type Output = FormalPowerSeries<T, C>;
298            fn $method(self, rhs: &FormalPowerSeries<T, C>) -> Self::Output {
299                $imp::$method(self.clone(), rhs.clone())
300            }
301        }
302    };
303}
304impl_fps_binop_conv!(Mul, mul, MulAssign, mul_assign);
305impl_fps_binop_conv!(Div, div, DivAssign, div_assign);
306impl_fps_binop_conv!(Rem, rem, RemAssign, rem_assign);
307
308impl<T, C> Neg for FormalPowerSeries<T, C>
309where
310    T: FormalPowerSeriesCoefficient,
311{
312    type Output = Self;
313    fn neg(mut self) -> Self::Output {
314        for x in self.iter_mut() {
315            *x = -x.clone();
316        }
317        self
318    }
319}
320impl<T, C> Neg for &FormalPowerSeries<T, C>
321where
322    T: FormalPowerSeriesCoefficient,
323{
324    type Output = FormalPowerSeries<T, C>;
325    fn neg(self) -> Self::Output {
326        self.clone().neg()
327    }
328}
329
330impl<T, C> ShrAssign<usize> for FormalPowerSeries<T, C>
331where
332    T: FormalPowerSeriesCoefficient,
333{
334    fn shr_assign(&mut self, rhs: usize) {
335        if self.length() <= rhs {
336            *self = Self::zero();
337        } else {
338            for i in rhs..self.length() {
339                self[i - rhs] = self[i].clone();
340            }
341            self.truncate(self.length() - rhs);
342        }
343    }
344}
345impl<T, C> ShlAssign<usize> for FormalPowerSeries<T, C>
346where
347    T: FormalPowerSeriesCoefficient,
348{
349    fn shl_assign(&mut self, rhs: usize) {
350        let n = self.length();
351        self.resize(n + rhs);
352        for i in (0..n).rev() {
353            self[i + rhs] = self[i].clone();
354        }
355        for i in 0..rhs {
356            self[i] = T::zero();
357        }
358    }
359}
360
361impl<T, C> Shr<usize> for FormalPowerSeries<T, C>
362where
363    T: FormalPowerSeriesCoefficient,
364{
365    type Output = Self;
366    fn shr(mut self, rhs: usize) -> Self::Output {
367        self.shr_assign(rhs);
368        self
369    }
370}
371impl<T, C> Shl<usize> for FormalPowerSeries<T, C>
372where
373    T: FormalPowerSeriesCoefficient,
374{
375    type Output = Self;
376    fn shl(mut self, rhs: usize) -> Self::Output {
377        self.shl_assign(rhs);
378        self
379    }
380}
381impl<T, C> Shr<usize> for &FormalPowerSeries<T, C>
382where
383    T: FormalPowerSeriesCoefficient,
384{
385    type Output = FormalPowerSeries<T, C>;
386    fn shr(self, rhs: usize) -> Self::Output {
387        if self.length() <= rhs {
388            Self::Output::zero()
389        } else {
390            let mut f = Self::Output::zeros(self.length() - rhs);
391            for i in rhs..self.length() {
392                f[i - rhs] = self[i].clone();
393            }
394            f
395        }
396    }
397}
398impl<T, C> Shl<usize> for &FormalPowerSeries<T, C>
399where
400    T: FormalPowerSeriesCoefficient,
401{
402    type Output = FormalPowerSeries<T, C>;
403    fn shl(self, rhs: usize) -> Self::Output {
404        let mut f = Self::Output::zeros(self.length() + rhs);
405        for (i, x) in self.iter().cloned().enumerate().rev() {
406            f[i + rhs] = x;
407        }
408        f
409    }

More examples

Hide additional examples

crates/competitive/src/math/formal_power_series/formal_power_series_impls.rs (line 226)

223    pub fn eval(&self, x: T) -> T {
224        let mut base = T::one();
225        let mut res = T::zero();
226        for a in self.iter() {
227            res += base.clone() * a.clone();
228            base *= x.clone();
229        }
230        res
231    }
232}
233
234impl<T, C> FormalPowerSeries<T, C>
235where
236    T: FormalPowerSeriesCoefficient,
237    C: ConvolveSteps<T = Vec<T>>,
238{
239    pub fn inv(&self, deg: usize) -> Self {
240        debug_assert!(!self[0].is_zero());
241        let mut f = Self::from(T::one() / self[0].clone());
242        let mut i = 1;
243        while i < deg {
244            let g = self.prefix_ref((i * 2).min(deg));
245            let h = f.clone();
246            let mut g = C::transform(g.data, 2 * i);
247            let h = C::transform(h.data, 2 * i);
248            C::multiply(&mut g, &h);
249            let mut g = Self::from_vec(C::inverse_transform(g, 2 * i));
250            g >>= i;
251            let mut g = C::transform(g.data, 2 * i);
252            C::multiply(&mut g, &h);
253            let g = Self::from_vec(C::inverse_transform(g, 2 * i));
254            f.data.extend((-g).into_iter().take(i));
255            i *= 2;
256        }
257        f.truncate(deg);
258        f
259    }
260    pub fn exp(&self, deg: usize) -> Self {
261        debug_assert!(self[0].is_zero());
262        let mut f = Self::one();
263        let mut i = 1;
264        while i < deg {
265            let mut g = -f.log(i * 2);
266            g[0] += T::one();
267            for (g, x) in g.iter_mut().zip(self.iter().take(i * 2)) {
268                *g += x.clone();
269            }
270            f = (f * g).prefix(i * 2);
271            i *= 2;
272        }
273        f.prefix(deg)
274    }
275    pub fn log(&self, deg: usize) -> Self {
276        (self.inv(deg) * self.clone().diff()).integral().prefix(deg)
277    }
278    pub fn pow(&self, rhs: usize, deg: usize) -> Self {
279        if rhs == 0 {
280            return Self::from_vec(
281                once(T::one())
282                    .chain(repeat_with(T::zero))
283                    .take(deg)
284                    .collect(),
285            );
286        }
287        if let Some(k) = self.iter().position(|x| !x.is_zero()) {
288            if k >= (deg + rhs - 1) / rhs {
289                Self::zeros(deg)
290            } else {
291                let mut x0 = self[k].clone();
292                let rev = T::one() / x0.clone();
293                let x = {
294                    let mut x = T::one();
295                    let mut y = rhs;
296                    while y > 0 {
297                        if y & 1 == 1 {
298                            x *= x0.clone();
299                        }
300                        x0 *= x0.clone();
301                        y >>= 1;
302                    }
303                    x
304                };
305                let mut f = (self.clone() * &rev) >> k;
306                f = (f.log(deg) * &T::from(rhs)).exp(deg) * &x;
307                f.truncate(deg - k * rhs);
308                f <<= k * rhs;
309                f
310            }
311        } else {
312            Self::zeros(deg)
313        }
314    }
315}
316
317impl<T, C> FormalPowerSeries<T, C>
318where
319    T: FormalPowerSeriesCoefficientSqrt,
320    C: ConvolveSteps<T = Vec<T>>,
321{
322    pub fn sqrt(&self, deg: usize) -> Option<Self> {
323        if self[0].is_zero() {
324            if let Some(k) = self.iter().position(|x| !x.is_zero()) {
325                if k % 2 != 0 {
326                    return None;
327                } else if deg > k / 2 {
328                    return Some((self >> k).sqrt(deg - k / 2)? << (k / 2));
329                }
330            }
331        } else {
332            let inv2 = T::one() / (T::one() + T::one());
333            let mut f = Self::from(self[0].sqrt_coefficient()?);
334            let mut i = 1;
335            while i < deg {
336                f = (&f + &(self.prefix_ref(i * 2) * f.inv(i * 2))).prefix(i * 2) * &inv2;
337                i *= 2;
338            }
339            f.truncate(deg);
340            return Some(f);
341        }
342        Some(Self::zeros(deg))
343    }
344}
345
346impl<T, C> FormalPowerSeries<T, C>
347where
348    T: FormalPowerSeriesCoefficient,
349    C: ConvolveSteps<T = Vec<T>>,
350{
351    pub fn count_subset_sum<F>(&self, deg: usize, mut inverse: F) -> Self
352    where
353        F: FnMut(usize) -> T,
354    {
355        let n = self.length();
356        let mut f = Self::zeros(n);
357        for i in 1..n {
358            if !self[i].is_zero() {
359                for (j, d) in (0..n).step_by(i).enumerate().skip(1) {
360                    if j & 1 != 0 {
361                        f[d] += self[i].clone() * &inverse(j);
362                    } else {
363                        f[d] -= self[i].clone() * &inverse(j);
364                    }
365                }
366            }
367        }
368        f.exp(deg)
369    }
370    pub fn count_multiset_sum<F>(&self, deg: usize, mut inverse: F) -> Self
371    where
372        F: FnMut(usize) -> T,
373    {
374        let n = self.length();
375        let mut f = Self::zeros(n);
376        for i in 1..n {
377            if !self[i].is_zero() {
378                for (j, d) in (0..n).step_by(i).enumerate().skip(1) {
379                    f[d] += self[i].clone() * &inverse(j);
380                }
381            }
382        }
383        f.exp(deg)
384    }
385    /// [x^n] P(x) / Q(x)
386    pub fn bostan_mori(self, rhs: Self, mut n: usize) -> T {
387        let mut p = self;
388        let mut q = rhs;
389        while n > 0 {
390            let mq = q.clone().parity_inversion();
391            let u = p * mq.clone();
392            p = if n % 2 == 0 { u.even() } else { u.odd() };
393            q = (q * mq).even();
394            n /= 2;
395        }
396        p[0].clone() / q[0].clone()
397    }
398    /// return F(x) where [x^n] P(x) / Q(x) = [x^d-1] P(x) F(x)
399    pub fn bostan_mori_msb(self, n: usize) -> Self {
400        let d = self.length() - 1;
401        if n == 0 {
402            return (Self::one() << (d - 1)) / self[0].clone();
403        }
404        let q = self;
405        let mq = q.clone().parity_inversion();
406        let w = (q * &mq).even().bostan_mori_msb(n / 2);
407        let mut s = Self::zeros(w.length() * 2 - (n % 2));
408        for (i, x) in w.iter().enumerate() {
409            s[i * 2 + (1 - n % 2)] = x.clone();
410        }
411        let len = 2 * d + 1;
412        let ts = C::transform(s.prefix(len).data, len);
413        mq.reversed().middle_product(&ts, len).prefix(d + 1)
414    }

Source

pub fn iter_mut(&mut self) -> IterMut<'_, T>

Examples found in repository ?

crates/competitive/src/math/formal_power_series/formal_power_series_nums.rs (line 40)

39    fn mul_assign(&mut self, rhs: T) {
40        for x in self.iter_mut() {
41            x.mul_assign(&rhs);
42        }
43    }
44}
45impl<T, C> DivAssign<T> for FormalPowerSeries<T, C>
46where
47    T: FormalPowerSeriesCoefficient,
48{
49    fn div_assign(&mut self, rhs: T) {
50        let rinv = T::one() / rhs;
51        for x in self.iter_mut() {
52            x.mul_assign(&rinv);
53        }
54    }
55}
56macro_rules! impl_fps_single_binop {
57    ($imp:ident, $method:ident, $imp_assign:ident, $method_assign:ident) => {
58        impl<T, C> $imp_assign<&T> for FormalPowerSeries<T, C>
59        where
60            T: FormalPowerSeriesCoefficient,
61        {
62            fn $method_assign(&mut self, rhs: &T) {
63                $imp_assign::$method_assign(self, rhs.clone());
64            }
65        }
66        impl<T, C> $imp<T> for FormalPowerSeries<T, C>
67        where
68            T: FormalPowerSeriesCoefficient,
69        {
70            type Output = Self;
71            fn $method(mut self, rhs: T) -> Self::Output {
72                $imp_assign::$method_assign(&mut self, rhs);
73                self
74            }
75        }
76        impl<T, C> $imp<&T> for FormalPowerSeries<T, C>
77        where
78            T: FormalPowerSeriesCoefficient,
79        {
80            type Output = Self;
81            fn $method(mut self, rhs: &T) -> Self::Output {
82                $imp_assign::$method_assign(&mut self, rhs);
83                self
84            }
85        }
86        impl<T, C> $imp<T> for &FormalPowerSeries<T, C>
87        where
88            T: FormalPowerSeriesCoefficient,
89        {
90            type Output = FormalPowerSeries<T, C>;
91            fn $method(self, rhs: T) -> Self::Output {
92                $imp::$method(self.clone(), rhs)
93            }
94        }
95        impl<T, C> $imp<&T> for &FormalPowerSeries<T, C>
96        where
97            T: FormalPowerSeriesCoefficient,
98        {
99            type Output = FormalPowerSeries<T, C>;
100            fn $method(self, rhs: &T) -> Self::Output {
101                $imp::$method(self.clone(), rhs)
102            }
103        }
104    };
105}
106impl_fps_single_binop!(Add, add, AddAssign, add_assign);
107impl_fps_single_binop!(Sub, sub, SubAssign, sub_assign);
108impl_fps_single_binop!(Mul, mul, MulAssign, mul_assign);
109impl_fps_single_binop!(Div, div, DivAssign, div_assign);
110
111impl<T, C> AddAssign<&Self> for FormalPowerSeries<T, C>
112where
113    T: FormalPowerSeriesCoefficient,
114{
115    fn add_assign(&mut self, rhs: &Self) {
116        if self.length() < rhs.length() {
117            self.resize(rhs.length());
118        }
119        for (x, y) in self.iter_mut().zip(rhs.iter()) {
120            x.add_assign(y);
121        }
122    }
123}
124impl<T, C> SubAssign<&Self> for FormalPowerSeries<T, C>
125where
126    T: FormalPowerSeriesCoefficient,
127{
128    fn sub_assign(&mut self, rhs: &Self) {
129        if self.length() < rhs.length() {
130            self.resize(rhs.length());
131        }
132        for (x, y) in self.iter_mut().zip(rhs.iter()) {
133            x.sub_assign(y);
134        }
135        self.trim_tail_zeros();
136    }
137}
138
139macro_rules! impl_fps_binop_addsub {
140    ($imp:ident, $method:ident, $imp_assign:ident, $method_assign:ident) => {
141        impl<T, C> $imp_assign for FormalPowerSeries<T, C>
142        where
143            T: FormalPowerSeriesCoefficient,
144        {
145            fn $method_assign(&mut self, rhs: Self) {
146                $imp_assign::$method_assign(self, &rhs);
147            }
148        }
149        impl<T, C> $imp for FormalPowerSeries<T, C>
150        where
151            T: FormalPowerSeriesCoefficient,
152        {
153            type Output = Self;
154            fn $method(mut self, rhs: Self) -> Self::Output {
155                $imp_assign::$method_assign(&mut self, &rhs);
156                self
157            }
158        }
159        impl<T, C> $imp<&FormalPowerSeries<T, C>> for FormalPowerSeries<T, C>
160        where
161            T: FormalPowerSeriesCoefficient,
162        {
163            type Output = Self;
164            fn $method(mut self, rhs: &FormalPowerSeries<T, C>) -> Self::Output {
165                $imp_assign::$method_assign(&mut self, rhs);
166                self
167            }
168        }
169        impl<T, C> $imp<FormalPowerSeries<T, C>> for &FormalPowerSeries<T, C>
170        where
171            T: FormalPowerSeriesCoefficient,
172        {
173            type Output = FormalPowerSeries<T, C>;
174            fn $method(self, rhs: FormalPowerSeries<T, C>) -> Self::Output {
175                let mut self_ = self.clone();
176                $imp_assign::$method_assign(&mut self_, &rhs);
177                self_
178            }
179        }
180        impl<T, C> $imp<&FormalPowerSeries<T, C>> for &FormalPowerSeries<T, C>
181        where
182            T: FormalPowerSeriesCoefficient,
183        {
184            type Output = FormalPowerSeries<T, C>;
185            fn $method(self, rhs: &FormalPowerSeries<T, C>) -> Self::Output {
186                let mut self_ = self.clone();
187                $imp_assign::$method_assign(&mut self_, rhs);
188                self_
189            }
190        }
191    };
192}
193impl_fps_binop_addsub!(Add, add, AddAssign, add_assign);
194impl_fps_binop_addsub!(Sub, sub, SubAssign, sub_assign);
195
196impl<T, C> Mul for FormalPowerSeries<T, C>
197where
198    C: ConvolveSteps<T = Vec<T>>,
199{
200    type Output = Self;
201    fn mul(self, rhs: Self) -> Self::Output {
202        Self::from_vec(C::convolve(self.data, rhs.data))
203    }
204}
205impl<T, C> Div for FormalPowerSeries<T, C>
206where
207    T: FormalPowerSeriesCoefficient,
208    C: ConvolveSteps<T = Vec<T>>,
209{
210    type Output = Self;
211    fn div(mut self, mut rhs: Self) -> Self::Output {
212        self.trim_tail_zeros();
213        rhs.trim_tail_zeros();
214        if self.length() < rhs.length() {
215            return Self::zero();
216        }
217        self.data.reverse();
218        rhs.data.reverse();
219        let n = self.length() - rhs.length() + 1;
220        let mut res = self * rhs.inv(n);
221        res.truncate(n);
222        res.data.reverse();
223        res
224    }
225}
226impl<T, C> Rem for FormalPowerSeries<T, C>
227where
228    T: FormalPowerSeriesCoefficient,
229    C: ConvolveSteps<T = Vec<T>>,
230{
231    type Output = Self;
232    fn rem(self, rhs: Self) -> Self::Output {
233        let mut rem = self.clone() - self / rhs.clone() * rhs;
234        rem.trim_tail_zeros();
235        rem
236    }
237}
238
239impl<T, C> FormalPowerSeries<T, C>
240where
241    T: FormalPowerSeriesCoefficient,
242    C: ConvolveSteps<T = Vec<T>>,
243{
244    pub fn div_rem(self, rhs: Self) -> (Self, Self) {
245        let div = self.clone() / rhs.clone();
246        let mut rem = self - div.clone() * rhs;
247        rem.trim_tail_zeros();
248        (div, rem)
249    }
250}
251
252macro_rules! impl_fps_binop_conv {
253    ($imp:ident, $method:ident, $imp_assign:ident, $method_assign:ident) => {
254        impl<T, C> $imp_assign for FormalPowerSeries<T, C>
255        where
256            T: FormalPowerSeriesCoefficient,
257            C: ConvolveSteps<T = Vec<T>>,
258        {
259            fn $method_assign(&mut self, rhs: Self) {
260                *self = $imp::$method(Self::from_vec(take(&mut self.data)), rhs);
261            }
262        }
263        impl<T, C> $imp_assign<&Self> for FormalPowerSeries<T, C>
264        where
265            T: FormalPowerSeriesCoefficient,
266            C: ConvolveSteps<T = Vec<T>>,
267        {
268            fn $method_assign(&mut self, rhs: &Self) {
269                $imp_assign::$method_assign(self, rhs.clone());
270            }
271        }
272        impl<T, C> $imp<&FormalPowerSeries<T, C>> for FormalPowerSeries<T, C>
273        where
274            T: FormalPowerSeriesCoefficient,
275            C: ConvolveSteps<T = Vec<T>>,
276        {
277            type Output = Self;
278            fn $method(self, rhs: &FormalPowerSeries<T, C>) -> Self::Output {
279                $imp::$method(self, rhs.clone())
280            }
281        }
282        impl<T, C> $imp<FormalPowerSeries<T, C>> for &FormalPowerSeries<T, C>
283        where
284            T: FormalPowerSeriesCoefficient,
285            C: ConvolveSteps<T = Vec<T>>,
286        {
287            type Output = FormalPowerSeries<T, C>;
288            fn $method(self, rhs: FormalPowerSeries<T, C>) -> Self::Output {
289                $imp::$method(self.clone(), rhs)
290            }
291        }
292        impl<T, C> $imp<&FormalPowerSeries<T, C>> for &FormalPowerSeries<T, C>
293        where
294            T: FormalPowerSeriesCoefficient,
295            C: ConvolveSteps<T = Vec<T>>,
296        {
297            type Output = FormalPowerSeries<T, C>;
298            fn $method(self, rhs: &FormalPowerSeries<T, C>) -> Self::Output {
299                $imp::$method(self.clone(), rhs.clone())
300            }
301        }
302    };
303}
304impl_fps_binop_conv!(Mul, mul, MulAssign, mul_assign);
305impl_fps_binop_conv!(Div, div, DivAssign, div_assign);
306impl_fps_binop_conv!(Rem, rem, RemAssign, rem_assign);
307
308impl<T, C> Neg for FormalPowerSeries<T, C>
309where
310    T: FormalPowerSeriesCoefficient,
311{
312    type Output = Self;
313    fn neg(mut self) -> Self::Output {
314        for x in self.iter_mut() {
315            *x = -x.clone();
316        }
317        self
318    }

More examples

Hide additional examples

crates/competitive/src/math/formal_power_series/formal_power_series_impls.rs (line 189)

187    pub fn diff(mut self) -> Self {
188        let mut c = T::one();
189        for x in self.iter_mut().skip(1) {
190            *x *= &c;
191            c += T::one();
192        }
193        if self.length() > 0 {
194            self.data.remove(0);
195        }
196        self
197    }
198    pub fn integral(mut self) -> Self {
199        let n = self.length();
200        self.data.insert(0, Zero::zero());
201        let mut fact = Vec::with_capacity(n + 1);
202        let mut c = T::one();
203        fact.push(c.clone());
204        for _ in 1..n {
205            fact.push(fact.last().cloned().unwrap() * c.clone());
206            c += T::one();
207        }
208        let mut invf = T::one() / (fact.last().cloned().unwrap() * c.clone());
209        for x in self.iter_mut().skip(1).rev() {
210            *x *= invf.clone() * fact.pop().unwrap();
211            invf *= c.clone();
212            c -= T::one();
213        }
214        self
215    }
216    pub fn parity_inversion(mut self) -> Self {
217        self.iter_mut()
218            .skip(1)
219            .step_by(2)
220            .for_each(|x| *x = -x.clone());
221        self
222    }
223    pub fn eval(&self, x: T) -> T {
224        let mut base = T::one();
225        let mut res = T::zero();
226        for a in self.iter() {
227            res += base.clone() * a.clone();
228            base *= x.clone();
229        }
230        res
231    }
232}
233
234impl<T, C> FormalPowerSeries<T, C>
235where
236    T: FormalPowerSeriesCoefficient,
237    C: ConvolveSteps<T = Vec<T>>,
238{
239    pub fn inv(&self, deg: usize) -> Self {
240        debug_assert!(!self[0].is_zero());
241        let mut f = Self::from(T::one() / self[0].clone());
242        let mut i = 1;
243        while i < deg {
244            let g = self.prefix_ref((i * 2).min(deg));
245            let h = f.clone();
246            let mut g = C::transform(g.data, 2 * i);
247            let h = C::transform(h.data, 2 * i);
248            C::multiply(&mut g, &h);
249            let mut g = Self::from_vec(C::inverse_transform(g, 2 * i));
250            g >>= i;
251            let mut g = C::transform(g.data, 2 * i);
252            C::multiply(&mut g, &h);
253            let g = Self::from_vec(C::inverse_transform(g, 2 * i));
254            f.data.extend((-g).into_iter().take(i));
255            i *= 2;
256        }
257        f.truncate(deg);
258        f
259    }
260    pub fn exp(&self, deg: usize) -> Self {
261        debug_assert!(self[0].is_zero());
262        let mut f = Self::one();
263        let mut i = 1;
264        while i < deg {
265            let mut g = -f.log(i * 2);
266            g[0] += T::one();
267            for (g, x) in g.iter_mut().zip(self.iter().take(i * 2)) {
268                *g += x.clone();
269            }
270            f = (f * g).prefix(i * 2);
271            i *= 2;
272        }
273        f.prefix(deg)
274    }

Source §

impl<T, C> FormalPowerSeries<T, C>
where T: Zero,

Source

pub fn zeros(deg: usize) -> Self

Examples found in repository ?

crates/competitive/src/math/formal_power_series/formal_power_series_nums.rs (line 390)

386    fn shr(self, rhs: usize) -> Self::Output {
387        if self.length() <= rhs {
388            Self::Output::zero()
389        } else {
390            let mut f = Self::Output::zeros(self.length() - rhs);
391            for i in rhs..self.length() {
392                f[i - rhs] = self[i].clone();
393            }
394            f
395        }
396    }
397}
398impl<T, C> Shl<usize> for &FormalPowerSeries<T, C>
399where
400    T: FormalPowerSeriesCoefficient,
401{
402    type Output = FormalPowerSeries<T, C>;
403    fn shl(self, rhs: usize) -> Self::Output {
404        let mut f = Self::Output::zeros(self.length() + rhs);
405        for (i, x) in self.iter().cloned().enumerate().rev() {
406            f[i + rhs] = x;
407        }
408        f
409    }

More examples

Hide additional examples

crates/competitive/src/math/formal_power_series/formal_power_series_impls.rs (line 289)

278    pub fn pow(&self, rhs: usize, deg: usize) -> Self {
279        if rhs == 0 {
280            return Self::from_vec(
281                once(T::one())
282                    .chain(repeat_with(T::zero))
283                    .take(deg)
284                    .collect(),
285            );
286        }
287        if let Some(k) = self.iter().position(|x| !x.is_zero()) {
288            if k >= (deg + rhs - 1) / rhs {
289                Self::zeros(deg)
290            } else {
291                let mut x0 = self[k].clone();
292                let rev = T::one() / x0.clone();
293                let x = {
294                    let mut x = T::one();
295                    let mut y = rhs;
296                    while y > 0 {
297                        if y & 1 == 1 {
298                            x *= x0.clone();
299                        }
300                        x0 *= x0.clone();
301                        y >>= 1;
302                    }
303                    x
304                };
305                let mut f = (self.clone() * &rev) >> k;
306                f = (f.log(deg) * &T::from(rhs)).exp(deg) * &x;
307                f.truncate(deg - k * rhs);
308                f <<= k * rhs;
309                f
310            }
311        } else {
312            Self::zeros(deg)
313        }
314    }
315}
316
317impl<T, C> FormalPowerSeries<T, C>
318where
319    T: FormalPowerSeriesCoefficientSqrt,
320    C: ConvolveSteps<T = Vec<T>>,
321{
322    pub fn sqrt(&self, deg: usize) -> Option<Self> {
323        if self[0].is_zero() {
324            if let Some(k) = self.iter().position(|x| !x.is_zero()) {
325                if k % 2 != 0 {
326                    return None;
327                } else if deg > k / 2 {
328                    return Some((self >> k).sqrt(deg - k / 2)? << (k / 2));
329                }
330            }
331        } else {
332            let inv2 = T::one() / (T::one() + T::one());
333            let mut f = Self::from(self[0].sqrt_coefficient()?);
334            let mut i = 1;
335            while i < deg {
336                f = (&f + &(self.prefix_ref(i * 2) * f.inv(i * 2))).prefix(i * 2) * &inv2;
337                i *= 2;
338            }
339            f.truncate(deg);
340            return Some(f);
341        }
342        Some(Self::zeros(deg))
343    }
344}
345
346impl<T, C> FormalPowerSeries<T, C>
347where
348    T: FormalPowerSeriesCoefficient,
349    C: ConvolveSteps<T = Vec<T>>,
350{
351    pub fn count_subset_sum<F>(&self, deg: usize, mut inverse: F) -> Self
352    where
353        F: FnMut(usize) -> T,
354    {
355        let n = self.length();
356        let mut f = Self::zeros(n);
357        for i in 1..n {
358            if !self[i].is_zero() {
359                for (j, d) in (0..n).step_by(i).enumerate().skip(1) {
360                    if j & 1 != 0 {
361                        f[d] += self[i].clone() * &inverse(j);
362                    } else {
363                        f[d] -= self[i].clone() * &inverse(j);
364                    }
365                }
366            }
367        }
368        f.exp(deg)
369    }
370    pub fn count_multiset_sum<F>(&self, deg: usize, mut inverse: F) -> Self
371    where
372        F: FnMut(usize) -> T,
373    {
374        let n = self.length();
375        let mut f = Self::zeros(n);
376        for i in 1..n {
377            if !self[i].is_zero() {
378                for (j, d) in (0..n).step_by(i).enumerate().skip(1) {
379                    f[d] += self[i].clone() * &inverse(j);
380                }
381            }
382        }
383        f.exp(deg)
384    }
385    /// [x^n] P(x) / Q(x)
386    pub fn bostan_mori(self, rhs: Self, mut n: usize) -> T {
387        let mut p = self;
388        let mut q = rhs;
389        while n > 0 {
390            let mq = q.clone().parity_inversion();
391            let u = p * mq.clone();
392            p = if n % 2 == 0 { u.even() } else { u.odd() };
393            q = (q * mq).even();
394            n /= 2;
395        }
396        p[0].clone() / q[0].clone()
397    }
398    /// return F(x) where [x^n] P(x) / Q(x) = [x^d-1] P(x) F(x)
399    pub fn bostan_mori_msb(self, n: usize) -> Self {
400        let d = self.length() - 1;
401        if n == 0 {
402            return (Self::one() << (d - 1)) / self[0].clone();
403        }
404        let q = self;
405        let mq = q.clone().parity_inversion();
406        let w = (q * &mq).even().bostan_mori_msb(n / 2);
407        let mut s = Self::zeros(w.length() * 2 - (n % 2));
408        for (i, x) in w.iter().enumerate() {
409            s[i * 2 + (1 - n % 2)] = x.clone();
410        }
411        let len = 2 * d + 1;
412        let ts = C::transform(s.prefix(len).data, len);
413        mq.reversed().middle_product(&ts, len).prefix(d + 1)
414    }

Source

pub fn resize(&mut self, deg: usize)

Examples found in repository ?

crates/competitive/src/math/formal_power_series/formal_power_series_impls.rs (line 62)

61    pub fn resized(mut self, deg: usize) -> Self {
62        self.resize(deg);
63        self
64    }

More examples

Hide additional examples

crates/competitive/src/math/formal_power_series/formal_power_series_nums.rs (line 117)

115    fn add_assign(&mut self, rhs: &Self) {
116        if self.length() < rhs.length() {
117            self.resize(rhs.length());
118        }
119        for (x, y) in self.iter_mut().zip(rhs.iter()) {
120            x.add_assign(y);
121        }
122    }
123}
124impl<T, C> SubAssign<&Self> for FormalPowerSeries<T, C>
125where
126    T: FormalPowerSeriesCoefficient,
127{
128    fn sub_assign(&mut self, rhs: &Self) {
129        if self.length() < rhs.length() {
130            self.resize(rhs.length());
131        }
132        for (x, y) in self.iter_mut().zip(rhs.iter()) {
133            x.sub_assign(y);
134        }
135        self.trim_tail_zeros();
136    }
137}
138
139macro_rules! impl_fps_binop_addsub {
140    ($imp:ident, $method:ident, $imp_assign:ident, $method_assign:ident) => {
141        impl<T, C> $imp_assign for FormalPowerSeries<T, C>
142        where
143            T: FormalPowerSeriesCoefficient,
144        {
145            fn $method_assign(&mut self, rhs: Self) {
146                $imp_assign::$method_assign(self, &rhs);
147            }
148        }
149        impl<T, C> $imp for FormalPowerSeries<T, C>
150        where
151            T: FormalPowerSeriesCoefficient,
152        {
153            type Output = Self;
154            fn $method(mut self, rhs: Self) -> Self::Output {
155                $imp_assign::$method_assign(&mut self, &rhs);
156                self
157            }
158        }
159        impl<T, C> $imp<&FormalPowerSeries<T, C>> for FormalPowerSeries<T, C>
160        where
161            T: FormalPowerSeriesCoefficient,
162        {
163            type Output = Self;
164            fn $method(mut self, rhs: &FormalPowerSeries<T, C>) -> Self::Output {
165                $imp_assign::$method_assign(&mut self, rhs);
166                self
167            }
168        }
169        impl<T, C> $imp<FormalPowerSeries<T, C>> for &FormalPowerSeries<T, C>
170        where
171            T: FormalPowerSeriesCoefficient,
172        {
173            type Output = FormalPowerSeries<T, C>;
174            fn $method(self, rhs: FormalPowerSeries<T, C>) -> Self::Output {
175                let mut self_ = self.clone();
176                $imp_assign::$method_assign(&mut self_, &rhs);
177                self_
178            }
179        }
180        impl<T, C> $imp<&FormalPowerSeries<T, C>> for &FormalPowerSeries<T, C>
181        where
182            T: FormalPowerSeriesCoefficient,
183        {
184            type Output = FormalPowerSeries<T, C>;
185            fn $method(self, rhs: &FormalPowerSeries<T, C>) -> Self::Output {
186                let mut self_ = self.clone();
187                $imp_assign::$method_assign(&mut self_, rhs);
188                self_
189            }
190        }
191    };
192}
193impl_fps_binop_addsub!(Add, add, AddAssign, add_assign);
194impl_fps_binop_addsub!(Sub, sub, SubAssign, sub_assign);
195
196impl<T, C> Mul for FormalPowerSeries<T, C>
197where
198    C: ConvolveSteps<T = Vec<T>>,
199{
200    type Output = Self;
201    fn mul(self, rhs: Self) -> Self::Output {
202        Self::from_vec(C::convolve(self.data, rhs.data))
203    }
204}
205impl<T, C> Div for FormalPowerSeries<T, C>
206where
207    T: FormalPowerSeriesCoefficient,
208    C: ConvolveSteps<T = Vec<T>>,
209{
210    type Output = Self;
211    fn div(mut self, mut rhs: Self) -> Self::Output {
212        self.trim_tail_zeros();
213        rhs.trim_tail_zeros();
214        if self.length() < rhs.length() {
215            return Self::zero();
216        }
217        self.data.reverse();
218        rhs.data.reverse();
219        let n = self.length() - rhs.length() + 1;
220        let mut res = self * rhs.inv(n);
221        res.truncate(n);
222        res.data.reverse();
223        res
224    }
225}
226impl<T, C> Rem for FormalPowerSeries<T, C>
227where
228    T: FormalPowerSeriesCoefficient,
229    C: ConvolveSteps<T = Vec<T>>,
230{
231    type Output = Self;
232    fn rem(self, rhs: Self) -> Self::Output {
233        let mut rem = self.clone() - self / rhs.clone() * rhs;
234        rem.trim_tail_zeros();
235        rem
236    }
237}
238
239impl<T, C> FormalPowerSeries<T, C>
240where
241    T: FormalPowerSeriesCoefficient,
242    C: ConvolveSteps<T = Vec<T>>,
243{
244    pub fn div_rem(self, rhs: Self) -> (Self, Self) {
245        let div = self.clone() / rhs.clone();
246        let mut rem = self - div.clone() * rhs;
247        rem.trim_tail_zeros();
248        (div, rem)
249    }
250}
251
252macro_rules! impl_fps_binop_conv {
253    ($imp:ident, $method:ident, $imp_assign:ident, $method_assign:ident) => {
254        impl<T, C> $imp_assign for FormalPowerSeries<T, C>
255        where
256            T: FormalPowerSeriesCoefficient,
257            C: ConvolveSteps<T = Vec<T>>,
258        {
259            fn $method_assign(&mut self, rhs: Self) {
260                *self = $imp::$method(Self::from_vec(take(&mut self.data)), rhs);
261            }
262        }
263        impl<T, C> $imp_assign<&Self> for FormalPowerSeries<T, C>
264        where
265            T: FormalPowerSeriesCoefficient,
266            C: ConvolveSteps<T = Vec<T>>,
267        {
268            fn $method_assign(&mut self, rhs: &Self) {
269                $imp_assign::$method_assign(self, rhs.clone());
270            }
271        }
272        impl<T, C> $imp<&FormalPowerSeries<T, C>> for FormalPowerSeries<T, C>
273        where
274            T: FormalPowerSeriesCoefficient,
275            C: ConvolveSteps<T = Vec<T>>,
276        {
277            type Output = Self;
278            fn $method(self, rhs: &FormalPowerSeries<T, C>) -> Self::Output {
279                $imp::$method(self, rhs.clone())
280            }
281        }
282        impl<T, C> $imp<FormalPowerSeries<T, C>> for &FormalPowerSeries<T, C>
283        where
284            T: FormalPowerSeriesCoefficient,
285            C: ConvolveSteps<T = Vec<T>>,
286        {
287            type Output = FormalPowerSeries<T, C>;
288            fn $method(self, rhs: FormalPowerSeries<T, C>) -> Self::Output {
289                $imp::$method(self.clone(), rhs)
290            }
291        }
292        impl<T, C> $imp<&FormalPowerSeries<T, C>> for &FormalPowerSeries<T, C>
293        where
294            T: FormalPowerSeriesCoefficient,
295            C: ConvolveSteps<T = Vec<T>>,
296        {
297            type Output = FormalPowerSeries<T, C>;
298            fn $method(self, rhs: &FormalPowerSeries<T, C>) -> Self::Output {
299                $imp::$method(self.clone(), rhs.clone())
300            }
301        }
302    };
303}
304impl_fps_binop_conv!(Mul, mul, MulAssign, mul_assign);
305impl_fps_binop_conv!(Div, div, DivAssign, div_assign);
306impl_fps_binop_conv!(Rem, rem, RemAssign, rem_assign);
307
308impl<T, C> Neg for FormalPowerSeries<T, C>
309where
310    T: FormalPowerSeriesCoefficient,
311{
312    type Output = Self;
313    fn neg(mut self) -> Self::Output {
314        for x in self.iter_mut() {
315            *x = -x.clone();
316        }
317        self
318    }
319}
320impl<T, C> Neg for &FormalPowerSeries<T, C>
321where
322    T: FormalPowerSeriesCoefficient,
323{
324    type Output = FormalPowerSeries<T, C>;
325    fn neg(self) -> Self::Output {
326        self.clone().neg()
327    }
328}
329
330impl<T, C> ShrAssign<usize> for FormalPowerSeries<T, C>
331where
332    T: FormalPowerSeriesCoefficient,
333{
334    fn shr_assign(&mut self, rhs: usize) {
335        if self.length() <= rhs {
336            *self = Self::zero();
337        } else {
338            for i in rhs..self.length() {
339                self[i - rhs] = self[i].clone();
340            }
341            self.truncate(self.length() - rhs);
342        }
343    }
344}
345impl<T, C> ShlAssign<usize> for FormalPowerSeries<T, C>
346where
347    T: FormalPowerSeriesCoefficient,
348{
349    fn shl_assign(&mut self, rhs: usize) {
350        let n = self.length();
351        self.resize(n + rhs);
352        for i in (0..n).rev() {
353            self[i + rhs] = self[i].clone();
354        }
355        for i in 0..rhs {
356            self[i] = T::zero();
357        }
358    }

Source

pub fn resized(self, deg: usize) -> Self

Examples found in repository ?

crates/competitive/src/math/formal_power_series/formal_power_series_impls.rs (line 448)

430    pub fn multipoint_evaluation(self, points: &[T]) -> Vec<T> {
431        let n = points.len();
432        if n <= 32 {
433            return points.iter().map(|p| self.eval(p.clone())).collect();
434        }
435        let mut subproduct_tree = Vec::with_capacity(n * 2);
436        subproduct_tree.resize_with(n, Zero::zero);
437        for x in points {
438            subproduct_tree.push(Self::from_vec(vec![-x.clone(), T::one()]));
439        }
440        for i in (1..n).rev() {
441            subproduct_tree[i] = &subproduct_tree[i * 2] * &subproduct_tree[i * 2 + 1];
442        }
443        let mut uptree_t = Vec::with_capacity(n * 2);
444        uptree_t.resize_with(1, Zero::zero);
445        subproduct_tree.reverse();
446        subproduct_tree.pop();
447        let m = self.length();
448        let v = subproduct_tree.pop().unwrap().reversed().resized(m);
449        let s = C::transform(self.data, m * 2);
450        uptree_t.push(v.inv(m).middle_product(&s, m * 2).resized(n).reversed());
451        for i in 1..n {
452            let subl = subproduct_tree.pop().unwrap();
453            let subr = subproduct_tree.pop().unwrap();
454            let (dl, dr) = (subl.length(), subr.length());
455            let len = dl.max(dr) + uptree_t[i].length();
456            let s = C::transform(uptree_t[i].data.to_vec(), len);
457            uptree_t.push(subr.middle_product(&s, len).prefix(dl));
458            uptree_t.push(subl.middle_product(&s, len).prefix(dr));
459        }
460        uptree_t[n..]
461            .iter()
462            .map(|u| u.data.first().cloned().unwrap_or_else(Zero::zero))
463            .collect()
464    }

Source

pub fn reversed(self) -> Self

Examples found in repository ?

crates/competitive/src/math/formal_power_series/formal_power_series_impls.rs (line 413)

399    pub fn bostan_mori_msb(self, n: usize) -> Self {
400        let d = self.length() - 1;
401        if n == 0 {
402            return (Self::one() << (d - 1)) / self[0].clone();
403        }
404        let q = self;
405        let mq = q.clone().parity_inversion();
406        let w = (q * &mq).even().bostan_mori_msb(n / 2);
407        let mut s = Self::zeros(w.length() * 2 - (n % 2));
408        for (i, x) in w.iter().enumerate() {
409            s[i * 2 + (1 - n % 2)] = x.clone();
410        }
411        let len = 2 * d + 1;
412        let ts = C::transform(s.prefix(len).data, len);
413        mq.reversed().middle_product(&ts, len).prefix(d + 1)
414    }
415    /// x^n mod self
416    pub fn pow_mod(self, n: usize) -> Self {
417        let d = self.length() - 1;
418        let q = self.reversed();
419        let u = q.clone().bostan_mori_msb(n);
420        let mut f = (u * q).prefix(d).reversed();
421        f.trim_tail_zeros();
422        f
423    }
424    fn middle_product(self, other: &C::F, deg: usize) -> Self {
425        let n = self.length();
426        let mut s = C::transform(self.reversed().data, deg);
427        C::multiply(&mut s, other);
428        Self::from_vec((C::inverse_transform(s, deg))[n - 1..].to_vec())
429    }
430    pub fn multipoint_evaluation(self, points: &[T]) -> Vec<T> {
431        let n = points.len();
432        if n <= 32 {
433            return points.iter().map(|p| self.eval(p.clone())).collect();
434        }
435        let mut subproduct_tree = Vec::with_capacity(n * 2);
436        subproduct_tree.resize_with(n, Zero::zero);
437        for x in points {
438            subproduct_tree.push(Self::from_vec(vec![-x.clone(), T::one()]));
439        }
440        for i in (1..n).rev() {
441            subproduct_tree[i] = &subproduct_tree[i * 2] * &subproduct_tree[i * 2 + 1];
442        }
443        let mut uptree_t = Vec::with_capacity(n * 2);
444        uptree_t.resize_with(1, Zero::zero);
445        subproduct_tree.reverse();
446        subproduct_tree.pop();
447        let m = self.length();
448        let v = subproduct_tree.pop().unwrap().reversed().resized(m);
449        let s = C::transform(self.data, m * 2);
450        uptree_t.push(v.inv(m).middle_product(&s, m * 2).resized(n).reversed());
451        for i in 1..n {
452            let subl = subproduct_tree.pop().unwrap();
453            let subr = subproduct_tree.pop().unwrap();
454            let (dl, dr) = (subl.length(), subr.length());
455            let len = dl.max(dr) + uptree_t[i].length();
456            let s = C::transform(uptree_t[i].data.to_vec(), len);
457            uptree_t.push(subr.middle_product(&s, len).prefix(dl));
458            uptree_t.push(subl.middle_product(&s, len).prefix(dr));
459        }
460        uptree_t[n..]
461            .iter()
462            .map(|u| u.data.first().cloned().unwrap_or_else(Zero::zero))
463            .collect()
464    }

Source §

impl<T, C> FormalPowerSeries<T, C>
where T: Zero + PartialEq,

Source

pub fn trim_tail_zeros(&mut self)

Examples found in repository ?

crates/competitive/src/math/formal_power_series/formal_power_series_nums.rs (line 32)

27    fn sub_assign(&mut self, rhs: T) {
28        if self.length() == 0 {
29            self.data.push(T::zero());
30        }
31        self.data[0].sub_assign(rhs);
32        self.trim_tail_zeros();
33    }
34}
35impl<T, C> MulAssign<T> for FormalPowerSeries<T, C>
36where
37    T: FormalPowerSeriesCoefficient,
38{
39    fn mul_assign(&mut self, rhs: T) {
40        for x in self.iter_mut() {
41            x.mul_assign(&rhs);
42        }
43    }
44}
45impl<T, C> DivAssign<T> for FormalPowerSeries<T, C>
46where
47    T: FormalPowerSeriesCoefficient,
48{
49    fn div_assign(&mut self, rhs: T) {
50        let rinv = T::one() / rhs;
51        for x in self.iter_mut() {
52            x.mul_assign(&rinv);
53        }
54    }
55}
56macro_rules! impl_fps_single_binop {
57    ($imp:ident, $method:ident, $imp_assign:ident, $method_assign:ident) => {
58        impl<T, C> $imp_assign<&T> for FormalPowerSeries<T, C>
59        where
60            T: FormalPowerSeriesCoefficient,
61        {
62            fn $method_assign(&mut self, rhs: &T) {
63                $imp_assign::$method_assign(self, rhs.clone());
64            }
65        }
66        impl<T, C> $imp<T> for FormalPowerSeries<T, C>
67        where
68            T: FormalPowerSeriesCoefficient,
69        {
70            type Output = Self;
71            fn $method(mut self, rhs: T) -> Self::Output {
72                $imp_assign::$method_assign(&mut self, rhs);
73                self
74            }
75        }
76        impl<T, C> $imp<&T> for FormalPowerSeries<T, C>
77        where
78            T: FormalPowerSeriesCoefficient,
79        {
80            type Output = Self;
81            fn $method(mut self, rhs: &T) -> Self::Output {
82                $imp_assign::$method_assign(&mut self, rhs);
83                self
84            }
85        }
86        impl<T, C> $imp<T> for &FormalPowerSeries<T, C>
87        where
88            T: FormalPowerSeriesCoefficient,
89        {
90            type Output = FormalPowerSeries<T, C>;
91            fn $method(self, rhs: T) -> Self::Output {
92                $imp::$method(self.clone(), rhs)
93            }
94        }
95        impl<T, C> $imp<&T> for &FormalPowerSeries<T, C>
96        where
97            T: FormalPowerSeriesCoefficient,
98        {
99            type Output = FormalPowerSeries<T, C>;
100            fn $method(self, rhs: &T) -> Self::Output {
101                $imp::$method(self.clone(), rhs)
102            }
103        }
104    };
105}
106impl_fps_single_binop!(Add, add, AddAssign, add_assign);
107impl_fps_single_binop!(Sub, sub, SubAssign, sub_assign);
108impl_fps_single_binop!(Mul, mul, MulAssign, mul_assign);
109impl_fps_single_binop!(Div, div, DivAssign, div_assign);
110
111impl<T, C> AddAssign<&Self> for FormalPowerSeries<T, C>
112where
113    T: FormalPowerSeriesCoefficient,
114{
115    fn add_assign(&mut self, rhs: &Self) {
116        if self.length() < rhs.length() {
117            self.resize(rhs.length());
118        }
119        for (x, y) in self.iter_mut().zip(rhs.iter()) {
120            x.add_assign(y);
121        }
122    }
123}
124impl<T, C> SubAssign<&Self> for FormalPowerSeries<T, C>
125where
126    T: FormalPowerSeriesCoefficient,
127{
128    fn sub_assign(&mut self, rhs: &Self) {
129        if self.length() < rhs.length() {
130            self.resize(rhs.length());
131        }
132        for (x, y) in self.iter_mut().zip(rhs.iter()) {
133            x.sub_assign(y);
134        }
135        self.trim_tail_zeros();
136    }
137}
138
139macro_rules! impl_fps_binop_addsub {
140    ($imp:ident, $method:ident, $imp_assign:ident, $method_assign:ident) => {
141        impl<T, C> $imp_assign for FormalPowerSeries<T, C>
142        where
143            T: FormalPowerSeriesCoefficient,
144        {
145            fn $method_assign(&mut self, rhs: Self) {
146                $imp_assign::$method_assign(self, &rhs);
147            }
148        }
149        impl<T, C> $imp for FormalPowerSeries<T, C>
150        where
151            T: FormalPowerSeriesCoefficient,
152        {
153            type Output = Self;
154            fn $method(mut self, rhs: Self) -> Self::Output {
155                $imp_assign::$method_assign(&mut self, &rhs);
156                self
157            }
158        }
159        impl<T, C> $imp<&FormalPowerSeries<T, C>> for FormalPowerSeries<T, C>
160        where
161            T: FormalPowerSeriesCoefficient,
162        {
163            type Output = Self;
164            fn $method(mut self, rhs: &FormalPowerSeries<T, C>) -> Self::Output {
165                $imp_assign::$method_assign(&mut self, rhs);
166                self
167            }
168        }
169        impl<T, C> $imp<FormalPowerSeries<T, C>> for &FormalPowerSeries<T, C>
170        where
171            T: FormalPowerSeriesCoefficient,
172        {
173            type Output = FormalPowerSeries<T, C>;
174            fn $method(self, rhs: FormalPowerSeries<T, C>) -> Self::Output {
175                let mut self_ = self.clone();
176                $imp_assign::$method_assign(&mut self_, &rhs);
177                self_
178            }
179        }
180        impl<T, C> $imp<&FormalPowerSeries<T, C>> for &FormalPowerSeries<T, C>
181        where
182            T: FormalPowerSeriesCoefficient,
183        {
184            type Output = FormalPowerSeries<T, C>;
185            fn $method(self, rhs: &FormalPowerSeries<T, C>) -> Self::Output {
186                let mut self_ = self.clone();
187                $imp_assign::$method_assign(&mut self_, rhs);
188                self_
189            }
190        }
191    };
192}
193impl_fps_binop_addsub!(Add, add, AddAssign, add_assign);
194impl_fps_binop_addsub!(Sub, sub, SubAssign, sub_assign);
195
196impl<T, C> Mul for FormalPowerSeries<T, C>
197where
198    C: ConvolveSteps<T = Vec<T>>,
199{
200    type Output = Self;
201    fn mul(self, rhs: Self) -> Self::Output {
202        Self::from_vec(C::convolve(self.data, rhs.data))
203    }
204}
205impl<T, C> Div for FormalPowerSeries<T, C>
206where
207    T: FormalPowerSeriesCoefficient,
208    C: ConvolveSteps<T = Vec<T>>,
209{
210    type Output = Self;
211    fn div(mut self, mut rhs: Self) -> Self::Output {
212        self.trim_tail_zeros();
213        rhs.trim_tail_zeros();
214        if self.length() < rhs.length() {
215            return Self::zero();
216        }
217        self.data.reverse();
218        rhs.data.reverse();
219        let n = self.length() - rhs.length() + 1;
220        let mut res = self * rhs.inv(n);
221        res.truncate(n);
222        res.data.reverse();
223        res
224    }
225}
226impl<T, C> Rem for FormalPowerSeries<T, C>
227where
228    T: FormalPowerSeriesCoefficient,
229    C: ConvolveSteps<T = Vec<T>>,
230{
231    type Output = Self;
232    fn rem(self, rhs: Self) -> Self::Output {
233        let mut rem = self.clone() - self / rhs.clone() * rhs;
234        rem.trim_tail_zeros();
235        rem
236    }
237}
238
239impl<T, C> FormalPowerSeries<T, C>
240where
241    T: FormalPowerSeriesCoefficient,
242    C: ConvolveSteps<T = Vec<T>>,
243{
244    pub fn div_rem(self, rhs: Self) -> (Self, Self) {
245        let div = self.clone() / rhs.clone();
246        let mut rem = self - div.clone() * rhs;
247        rem.trim_tail_zeros();
248        (div, rem)
249    }

More examples

Hide additional examples

crates/competitive/src/math/formal_power_series/formal_power_series_impls.rs (line 421)

416    pub fn pow_mod(self, n: usize) -> Self {
417        let d = self.length() - 1;
418        let q = self.reversed();
419        let u = q.clone().bostan_mori_msb(n);
420        let mut f = (u * q).prefix(d).reversed();
421        f.trim_tail_zeros();
422        f
423    }

Source §

impl<T, C> FormalPowerSeries<T, C>
where T: FormalPowerSeriesCoefficient,

Source

pub fn prefix_ref(&self, deg: usize) -> Self

Examples found in repository ?

crates/competitive/src/math/formal_power_series/formal_power_series_impls.rs (line 244)

239    pub fn inv(&self, deg: usize) -> Self {
240        debug_assert!(!self[0].is_zero());
241        let mut f = Self::from(T::one() / self[0].clone());
242        let mut i = 1;
243        while i < deg {
244            let g = self.prefix_ref((i * 2).min(deg));
245            let h = f.clone();
246            let mut g = C::transform(g.data, 2 * i);
247            let h = C::transform(h.data, 2 * i);
248            C::multiply(&mut g, &h);
249            let mut g = Self::from_vec(C::inverse_transform(g, 2 * i));
250            g >>= i;
251            let mut g = C::transform(g.data, 2 * i);
252            C::multiply(&mut g, &h);
253            let g = Self::from_vec(C::inverse_transform(g, 2 * i));
254            f.data.extend((-g).into_iter().take(i));
255            i *= 2;
256        }
257        f.truncate(deg);
258        f
259    }
260    pub fn exp(&self, deg: usize) -> Self {
261        debug_assert!(self[0].is_zero());
262        let mut f = Self::one();
263        let mut i = 1;
264        while i < deg {
265            let mut g = -f.log(i * 2);
266            g[0] += T::one();
267            for (g, x) in g.iter_mut().zip(self.iter().take(i * 2)) {
268                *g += x.clone();
269            }
270            f = (f * g).prefix(i * 2);
271            i *= 2;
272        }
273        f.prefix(deg)
274    }
275    pub fn log(&self, deg: usize) -> Self {
276        (self.inv(deg) * self.clone().diff()).integral().prefix(deg)
277    }
278    pub fn pow(&self, rhs: usize, deg: usize) -> Self {
279        if rhs == 0 {
280            return Self::from_vec(
281                once(T::one())
282                    .chain(repeat_with(T::zero))
283                    .take(deg)
284                    .collect(),
285            );
286        }
287        if let Some(k) = self.iter().position(|x| !x.is_zero()) {
288            if k >= (deg + rhs - 1) / rhs {
289                Self::zeros(deg)
290            } else {
291                let mut x0 = self[k].clone();
292                let rev = T::one() / x0.clone();
293                let x = {
294                    let mut x = T::one();
295                    let mut y = rhs;
296                    while y > 0 {
297                        if y & 1 == 1 {
298                            x *= x0.clone();
299                        }
300                        x0 *= x0.clone();
301                        y >>= 1;
302                    }
303                    x
304                };
305                let mut f = (self.clone() * &rev) >> k;
306                f = (f.log(deg) * &T::from(rhs)).exp(deg) * &x;
307                f.truncate(deg - k * rhs);
308                f <<= k * rhs;
309                f
310            }
311        } else {
312            Self::zeros(deg)
313        }
314    }
315}
316
317impl<T, C> FormalPowerSeries<T, C>
318where
319    T: FormalPowerSeriesCoefficientSqrt,
320    C: ConvolveSteps<T = Vec<T>>,
321{
322    pub fn sqrt(&self, deg: usize) -> Option<Self> {
323        if self[0].is_zero() {
324            if let Some(k) = self.iter().position(|x| !x.is_zero()) {
325                if k % 2 != 0 {
326                    return None;
327                } else if deg > k / 2 {
328                    return Some((self >> k).sqrt(deg - k / 2)? << (k / 2));
329                }
330            }
331        } else {
332            let inv2 = T::one() / (T::one() + T::one());
333            let mut f = Self::from(self[0].sqrt_coefficient()?);
334            let mut i = 1;
335            while i < deg {
336                f = (&f + &(self.prefix_ref(i * 2) * f.inv(i * 2))).prefix(i * 2) * &inv2;
337                i *= 2;
338            }
339            f.truncate(deg);
340            return Some(f);
341        }
342        Some(Self::zeros(deg))
343    }

Source

pub fn prefix(self, deg: usize) -> Self

Examples found in repository ?

crates/competitive/src/math/formal_power_series/formal_power_series_impls.rs (line 270)

260    pub fn exp(&self, deg: usize) -> Self {
261        debug_assert!(self[0].is_zero());
262        let mut f = Self::one();
263        let mut i = 1;
264        while i < deg {
265            let mut g = -f.log(i * 2);
266            g[0] += T::one();
267            for (g, x) in g.iter_mut().zip(self.iter().take(i * 2)) {
268                *g += x.clone();
269            }
270            f = (f * g).prefix(i * 2);
271            i *= 2;
272        }
273        f.prefix(deg)
274    }
275    pub fn log(&self, deg: usize) -> Self {
276        (self.inv(deg) * self.clone().diff()).integral().prefix(deg)
277    }
278    pub fn pow(&self, rhs: usize, deg: usize) -> Self {
279        if rhs == 0 {
280            return Self::from_vec(
281                once(T::one())
282                    .chain(repeat_with(T::zero))
283                    .take(deg)
284                    .collect(),
285            );
286        }
287        if let Some(k) = self.iter().position(|x| !x.is_zero()) {
288            if k >= (deg + rhs - 1) / rhs {
289                Self::zeros(deg)
290            } else {
291                let mut x0 = self[k].clone();
292                let rev = T::one() / x0.clone();
293                let x = {
294                    let mut x = T::one();
295                    let mut y = rhs;
296                    while y > 0 {
297                        if y & 1 == 1 {
298                            x *= x0.clone();
299                        }
300                        x0 *= x0.clone();
301                        y >>= 1;
302                    }
303                    x
304                };
305                let mut f = (self.clone() * &rev) >> k;
306                f = (f.log(deg) * &T::from(rhs)).exp(deg) * &x;
307                f.truncate(deg - k * rhs);
308                f <<= k * rhs;
309                f
310            }
311        } else {
312            Self::zeros(deg)
313        }
314    }
315}
316
317impl<T, C> FormalPowerSeries<T, C>
318where
319    T: FormalPowerSeriesCoefficientSqrt,
320    C: ConvolveSteps<T = Vec<T>>,
321{
322    pub fn sqrt(&self, deg: usize) -> Option<Self> {
323        if self[0].is_zero() {
324            if let Some(k) = self.iter().position(|x| !x.is_zero()) {
325                if k % 2 != 0 {
326                    return None;
327                } else if deg > k / 2 {
328                    return Some((self >> k).sqrt(deg - k / 2)? << (k / 2));
329                }
330            }
331        } else {
332            let inv2 = T::one() / (T::one() + T::one());
333            let mut f = Self::from(self[0].sqrt_coefficient()?);
334            let mut i = 1;
335            while i < deg {
336                f = (&f + &(self.prefix_ref(i * 2) * f.inv(i * 2))).prefix(i * 2) * &inv2;
337                i *= 2;
338            }
339            f.truncate(deg);
340            return Some(f);
341        }
342        Some(Self::zeros(deg))
343    }
344}
345
346impl<T, C> FormalPowerSeries<T, C>
347where
348    T: FormalPowerSeriesCoefficient,
349    C: ConvolveSteps<T = Vec<T>>,
350{
351    pub fn count_subset_sum<F>(&self, deg: usize, mut inverse: F) -> Self
352    where
353        F: FnMut(usize) -> T,
354    {
355        let n = self.length();
356        let mut f = Self::zeros(n);
357        for i in 1..n {
358            if !self[i].is_zero() {
359                for (j, d) in (0..n).step_by(i).enumerate().skip(1) {
360                    if j & 1 != 0 {
361                        f[d] += self[i].clone() * &inverse(j);
362                    } else {
363                        f[d] -= self[i].clone() * &inverse(j);
364                    }
365                }
366            }
367        }
368        f.exp(deg)
369    }
370    pub fn count_multiset_sum<F>(&self, deg: usize, mut inverse: F) -> Self
371    where
372        F: FnMut(usize) -> T,
373    {
374        let n = self.length();
375        let mut f = Self::zeros(n);
376        for i in 1..n {
377            if !self[i].is_zero() {
378                for (j, d) in (0..n).step_by(i).enumerate().skip(1) {
379                    f[d] += self[i].clone() * &inverse(j);
380                }
381            }
382        }
383        f.exp(deg)
384    }
385    /// [x^n] P(x) / Q(x)
386    pub fn bostan_mori(self, rhs: Self, mut n: usize) -> T {
387        let mut p = self;
388        let mut q = rhs;
389        while n > 0 {
390            let mq = q.clone().parity_inversion();
391            let u = p * mq.clone();
392            p = if n % 2 == 0 { u.even() } else { u.odd() };
393            q = (q * mq).even();
394            n /= 2;
395        }
396        p[0].clone() / q[0].clone()
397    }
398    /// return F(x) where [x^n] P(x) / Q(x) = [x^d-1] P(x) F(x)
399    pub fn bostan_mori_msb(self, n: usize) -> Self {
400        let d = self.length() - 1;
401        if n == 0 {
402            return (Self::one() << (d - 1)) / self[0].clone();
403        }
404        let q = self;
405        let mq = q.clone().parity_inversion();
406        let w = (q * &mq).even().bostan_mori_msb(n / 2);
407        let mut s = Self::zeros(w.length() * 2 - (n % 2));
408        for (i, x) in w.iter().enumerate() {
409            s[i * 2 + (1 - n % 2)] = x.clone();
410        }
411        let len = 2 * d + 1;
412        let ts = C::transform(s.prefix(len).data, len);
413        mq.reversed().middle_product(&ts, len).prefix(d + 1)
414    }
415    /// x^n mod self
416    pub fn pow_mod(self, n: usize) -> Self {
417        let d = self.length() - 1;
418        let q = self.reversed();
419        let u = q.clone().bostan_mori_msb(n);
420        let mut f = (u * q).prefix(d).reversed();
421        f.trim_tail_zeros();
422        f
423    }
424    fn middle_product(self, other: &C::F, deg: usize) -> Self {
425        let n = self.length();
426        let mut s = C::transform(self.reversed().data, deg);
427        C::multiply(&mut s, other);
428        Self::from_vec((C::inverse_transform(s, deg))[n - 1..].to_vec())
429    }
430    pub fn multipoint_evaluation(self, points: &[T]) -> Vec<T> {
431        let n = points.len();
432        if n <= 32 {
433            return points.iter().map(|p| self.eval(p.clone())).collect();
434        }
435        let mut subproduct_tree = Vec::with_capacity(n * 2);
436        subproduct_tree.resize_with(n, Zero::zero);
437        for x in points {
438            subproduct_tree.push(Self::from_vec(vec![-x.clone(), T::one()]));
439        }
440        for i in (1..n).rev() {
441            subproduct_tree[i] = &subproduct_tree[i * 2] * &subproduct_tree[i * 2 + 1];
442        }
443        let mut uptree_t = Vec::with_capacity(n * 2);
444        uptree_t.resize_with(1, Zero::zero);
445        subproduct_tree.reverse();
446        subproduct_tree.pop();
447        let m = self.length();
448        let v = subproduct_tree.pop().unwrap().reversed().resized(m);
449        let s = C::transform(self.data, m * 2);
450        uptree_t.push(v.inv(m).middle_product(&s, m * 2).resized(n).reversed());
451        for i in 1..n {
452            let subl = subproduct_tree.pop().unwrap();
453            let subr = subproduct_tree.pop().unwrap();
454            let (dl, dr) = (subl.length(), subr.length());
455            let len = dl.max(dr) + uptree_t[i].length();
456            let s = C::transform(uptree_t[i].data.to_vec(), len);
457            uptree_t.push(subr.middle_product(&s, len).prefix(dl));
458            uptree_t.push(subl.middle_product(&s, len).prefix(dr));
459        }
460        uptree_t[n..]
461            .iter()
462            .map(|u| u.data.first().cloned().unwrap_or_else(Zero::zero))
463            .collect()
464    }
465    pub fn product_all<I>(iter: I, deg: usize) -> Self
466    where
467        I: IntoIterator<Item = Self>,
468    {
469        let mut heap: BinaryHeap<_> = iter
470            .into_iter()
471            .map(|f| PartialIgnoredOrd(Reverse(f.length()), f))
472            .collect();
473        while let Some(PartialIgnoredOrd(_, x)) = heap.pop() {
474            if let Some(PartialIgnoredOrd(_, y)) = heap.pop() {
475                let z = (x * y).prefix(deg);
476                heap.push(PartialIgnoredOrd(Reverse(z.length()), z));
477            } else {
478                return x;
479            }
480        }
481        Self::one()
482    }
483    pub fn sum_all_rational<I>(iter: I, deg: usize) -> (Self, Self)
484    where
485        I: IntoIterator<Item = (Self, Self)>,
486    {
487        let mut heap: BinaryHeap<_> = iter
488            .into_iter()
489            .map(|(f, g)| PartialIgnoredOrd(Reverse(f.length().max(g.length())), (f, g)))
490            .collect();
491        while let Some(PartialIgnoredOrd(_, (xa, xb))) = heap.pop() {
492            if let Some(PartialIgnoredOrd(_, (ya, yb))) = heap.pop() {
493                let zb = (&xb * &yb).prefix(deg);
494                let za = (xa * yb + ya * xb).prefix(deg);
495                heap.push(PartialIgnoredOrd(
496                    Reverse(za.length().max(zb.length())),
497                    (za, zb),
498                ));
499            } else {
500                return (xa, xb);
501            }
502        }
503        (Self::zero(), Self::one())
504    }
505    pub fn kth_term_of_linearly_recurrence(self, a: Vec<T>, k: usize) -> T {
506        if let Some(x) = a.get(k) {
507            return x.clone();
508        }
509        let p = (Self::from_vec(a).prefix(self.length() - 1) * &self).prefix(self.length() - 1);
510        p.bostan_mori(self, k)
511    }
512    pub fn kth_term(a: Vec<T>, k: usize) -> T {
513        if let Some(x) = a.get(k) {
514            return x.clone();
515        }
516        Self::from_vec(berlekamp_massey(&a)).kth_term_of_linearly_recurrence(a, k)
517    }
518    /// sum_i a_i exp(b_i x)
519    pub fn linear_sum_of_exp<I, F>(iter: I, deg: usize, mut inv_fact: F) -> Self
520    where
521        I: IntoIterator<Item = (T, T)>,
522        F: FnMut(usize) -> T,
523    {
524        let (p, q) = Self::sum_all_rational(
525            iter.into_iter()
526                .map(|(a, b)| (Self::from_vec(vec![a]), Self::from_vec(vec![T::one(), -b]))),
527            deg,
528        );
529        let mut f = (p * q.inv(deg)).prefix(deg);
530        for i in 0..f.length() {
531            f[i] *= inv_fact(i);
532        }
533        f
534    }

Source

pub fn even(self) -> Self

Examples found in repository ?

crates/competitive/src/math/formal_power_series/formal_power_series_impls.rs (line 392)

386    pub fn bostan_mori(self, rhs: Self, mut n: usize) -> T {
387        let mut p = self;
388        let mut q = rhs;
389        while n > 0 {
390            let mq = q.clone().parity_inversion();
391            let u = p * mq.clone();
392            p = if n % 2 == 0 { u.even() } else { u.odd() };
393            q = (q * mq).even();
394            n /= 2;
395        }
396        p[0].clone() / q[0].clone()
397    }
398    /// return F(x) where [x^n] P(x) / Q(x) = [x^d-1] P(x) F(x)
399    pub fn bostan_mori_msb(self, n: usize) -> Self {
400        let d = self.length() - 1;
401        if n == 0 {
402            return (Self::one() << (d - 1)) / self[0].clone();
403        }
404        let q = self;
405        let mq = q.clone().parity_inversion();
406        let w = (q * &mq).even().bostan_mori_msb(n / 2);
407        let mut s = Self::zeros(w.length() * 2 - (n % 2));
408        for (i, x) in w.iter().enumerate() {
409            s[i * 2 + (1 - n % 2)] = x.clone();
410        }
411        let len = 2 * d + 1;
412        let ts = C::transform(s.prefix(len).data, len);
413        mq.reversed().middle_product(&ts, len).prefix(d + 1)
414    }

Source

pub fn odd(self) -> Self

Examples found in repository ?

crates/competitive/src/math/formal_power_series/formal_power_series_impls.rs (line 392)

386    pub fn bostan_mori(self, rhs: Self, mut n: usize) -> T {
387        let mut p = self;
388        let mut q = rhs;
389        while n > 0 {
390            let mq = q.clone().parity_inversion();
391            let u = p * mq.clone();
392            p = if n % 2 == 0 { u.even() } else { u.odd() };
393            q = (q * mq).even();
394            n /= 2;
395        }
396        p[0].clone() / q[0].clone()
397    }

Source

pub fn diff(self) -> Self

Examples found in repository ?

crates/competitive/src/math/formal_power_series/formal_power_series_impls.rs (line 276)

275    pub fn log(&self, deg: usize) -> Self {
276        (self.inv(deg) * self.clone().diff()).integral().prefix(deg)
277    }

Source

pub fn integral(self) -> Self

Examples found in repository ?

crates/competitive/src/math/formal_power_series/formal_power_series_impls.rs (line 276)

275    pub fn log(&self, deg: usize) -> Self {
276        (self.inv(deg) * self.clone().diff()).integral().prefix(deg)
277    }

Source

pub fn parity_inversion(self) -> Self

Examples found in repository ?

crates/competitive/src/math/formal_power_series/formal_power_series_impls.rs (line 390)

386    pub fn bostan_mori(self, rhs: Self, mut n: usize) -> T {
387        let mut p = self;
388        let mut q = rhs;
389        while n > 0 {
390            let mq = q.clone().parity_inversion();
391            let u = p * mq.clone();
392            p = if n % 2 == 0 { u.even() } else { u.odd() };
393            q = (q * mq).even();
394            n /= 2;
395        }
396        p[0].clone() / q[0].clone()
397    }
398    /// return F(x) where [x^n] P(x) / Q(x) = [x^d-1] P(x) F(x)
399    pub fn bostan_mori_msb(self, n: usize) -> Self {
400        let d = self.length() - 1;
401        if n == 0 {
402            return (Self::one() << (d - 1)) / self[0].clone();
403        }
404        let q = self;
405        let mq = q.clone().parity_inversion();
406        let w = (q * &mq).even().bostan_mori_msb(n / 2);
407        let mut s = Self::zeros(w.length() * 2 - (n % 2));
408        for (i, x) in w.iter().enumerate() {
409            s[i * 2 + (1 - n % 2)] = x.clone();
410        }
411        let len = 2 * d + 1;
412        let ts = C::transform(s.prefix(len).data, len);
413        mq.reversed().middle_product(&ts, len).prefix(d + 1)
414    }

Source

pub fn eval(&self, x: T) -> T

Examples found in repository ?

crates/competitive/src/math/formal_power_series/formal_power_series_impls.rs (line 433)

430    pub fn multipoint_evaluation(self, points: &[T]) -> Vec<T> {
431        let n = points.len();
432        if n <= 32 {
433            return points.iter().map(|p| self.eval(p.clone())).collect();
434        }
435        let mut subproduct_tree = Vec::with_capacity(n * 2);
436        subproduct_tree.resize_with(n, Zero::zero);
437        for x in points {
438            subproduct_tree.push(Self::from_vec(vec![-x.clone(), T::one()]));
439        }
440        for i in (1..n).rev() {
441            subproduct_tree[i] = &subproduct_tree[i * 2] * &subproduct_tree[i * 2 + 1];
442        }
443        let mut uptree_t = Vec::with_capacity(n * 2);
444        uptree_t.resize_with(1, Zero::zero);
445        subproduct_tree.reverse();
446        subproduct_tree.pop();
447        let m = self.length();
448        let v = subproduct_tree.pop().unwrap().reversed().resized(m);
449        let s = C::transform(self.data, m * 2);
450        uptree_t.push(v.inv(m).middle_product(&s, m * 2).resized(n).reversed());
451        for i in 1..n {
452            let subl = subproduct_tree.pop().unwrap();
453            let subr = subproduct_tree.pop().unwrap();
454            let (dl, dr) = (subl.length(), subr.length());
455            let len = dl.max(dr) + uptree_t[i].length();
456            let s = C::transform(uptree_t[i].data.to_vec(), len);
457            uptree_t.push(subr.middle_product(&s, len).prefix(dl));
458            uptree_t.push(subl.middle_product(&s, len).prefix(dr));
459        }
460        uptree_t[n..]
461            .iter()
462            .map(|u| u.data.first().cloned().unwrap_or_else(Zero::zero))
463            .collect()
464    }

Source §

impl<T, C> FormalPowerSeries<T, C>
where T: FormalPowerSeriesCoefficient, C: ConvolveSteps<T = Vec<T>>,

Source

pub fn inv(&self, deg: usize) -> Self

Examples found in repository ?

crates/competitive/src/math/formal_power_series/formal_power_series_impls.rs (line 276)

275    pub fn log(&self, deg: usize) -> Self {
276        (self.inv(deg) * self.clone().diff()).integral().prefix(deg)
277    }
278    pub fn pow(&self, rhs: usize, deg: usize) -> Self {
279        if rhs == 0 {
280            return Self::from_vec(
281                once(T::one())
282                    .chain(repeat_with(T::zero))
283                    .take(deg)
284                    .collect(),
285            );
286        }
287        if let Some(k) = self.iter().position(|x| !x.is_zero()) {
288            if k >= (deg + rhs - 1) / rhs {
289                Self::zeros(deg)
290            } else {
291                let mut x0 = self[k].clone();
292                let rev = T::one() / x0.clone();
293                let x = {
294                    let mut x = T::one();
295                    let mut y = rhs;
296                    while y > 0 {
297                        if y & 1 == 1 {
298                            x *= x0.clone();
299                        }
300                        x0 *= x0.clone();
301                        y >>= 1;
302                    }
303                    x
304                };
305                let mut f = (self.clone() * &rev) >> k;
306                f = (f.log(deg) * &T::from(rhs)).exp(deg) * &x;
307                f.truncate(deg - k * rhs);
308                f <<= k * rhs;
309                f
310            }
311        } else {
312            Self::zeros(deg)
313        }
314    }
315}
316
317impl<T, C> FormalPowerSeries<T, C>
318where
319    T: FormalPowerSeriesCoefficientSqrt,
320    C: ConvolveSteps<T = Vec<T>>,
321{
322    pub fn sqrt(&self, deg: usize) -> Option<Self> {
323        if self[0].is_zero() {
324            if let Some(k) = self.iter().position(|x| !x.is_zero()) {
325                if k % 2 != 0 {
326                    return None;
327                } else if deg > k / 2 {
328                    return Some((self >> k).sqrt(deg - k / 2)? << (k / 2));
329                }
330            }
331        } else {
332            let inv2 = T::one() / (T::one() + T::one());
333            let mut f = Self::from(self[0].sqrt_coefficient()?);
334            let mut i = 1;
335            while i < deg {
336                f = (&f + &(self.prefix_ref(i * 2) * f.inv(i * 2))).prefix(i * 2) * &inv2;
337                i *= 2;
338            }
339            f.truncate(deg);
340            return Some(f);
341        }
342        Some(Self::zeros(deg))
343    }
344}
345
346impl<T, C> FormalPowerSeries<T, C>
347where
348    T: FormalPowerSeriesCoefficient,
349    C: ConvolveSteps<T = Vec<T>>,
350{
351    pub fn count_subset_sum<F>(&self, deg: usize, mut inverse: F) -> Self
352    where
353        F: FnMut(usize) -> T,
354    {
355        let n = self.length();
356        let mut f = Self::zeros(n);
357        for i in 1..n {
358            if !self[i].is_zero() {
359                for (j, d) in (0..n).step_by(i).enumerate().skip(1) {
360                    if j & 1 != 0 {
361                        f[d] += self[i].clone() * &inverse(j);
362                    } else {
363                        f[d] -= self[i].clone() * &inverse(j);
364                    }
365                }
366            }
367        }
368        f.exp(deg)
369    }
370    pub fn count_multiset_sum<F>(&self, deg: usize, mut inverse: F) -> Self
371    where
372        F: FnMut(usize) -> T,
373    {
374        let n = self.length();
375        let mut f = Self::zeros(n);
376        for i in 1..n {
377            if !self[i].is_zero() {
378                for (j, d) in (0..n).step_by(i).enumerate().skip(1) {
379                    f[d] += self[i].clone() * &inverse(j);
380                }
381            }
382        }
383        f.exp(deg)
384    }
385    /// [x^n] P(x) / Q(x)
386    pub fn bostan_mori(self, rhs: Self, mut n: usize) -> T {
387        let mut p = self;
388        let mut q = rhs;
389        while n > 0 {
390            let mq = q.clone().parity_inversion();
391            let u = p * mq.clone();
392            p = if n % 2 == 0 { u.even() } else { u.odd() };
393            q = (q * mq).even();
394            n /= 2;
395        }
396        p[0].clone() / q[0].clone()
397    }
398    /// return F(x) where [x^n] P(x) / Q(x) = [x^d-1] P(x) F(x)
399    pub fn bostan_mori_msb(self, n: usize) -> Self {
400        let d = self.length() - 1;
401        if n == 0 {
402            return (Self::one() << (d - 1)) / self[0].clone();
403        }
404        let q = self;
405        let mq = q.clone().parity_inversion();
406        let w = (q * &mq).even().bostan_mori_msb(n / 2);
407        let mut s = Self::zeros(w.length() * 2 - (n % 2));
408        for (i, x) in w.iter().enumerate() {
409            s[i * 2 + (1 - n % 2)] = x.clone();
410        }
411        let len = 2 * d + 1;
412        let ts = C::transform(s.prefix(len).data, len);
413        mq.reversed().middle_product(&ts, len).prefix(d + 1)
414    }
415    /// x^n mod self
416    pub fn pow_mod(self, n: usize) -> Self {
417        let d = self.length() - 1;
418        let q = self.reversed();
419        let u = q.clone().bostan_mori_msb(n);
420        let mut f = (u * q).prefix(d).reversed();
421        f.trim_tail_zeros();
422        f
423    }
424    fn middle_product(self, other: &C::F, deg: usize) -> Self {
425        let n = self.length();
426        let mut s = C::transform(self.reversed().data, deg);
427        C::multiply(&mut s, other);
428        Self::from_vec((C::inverse_transform(s, deg))[n - 1..].to_vec())
429    }
430    pub fn multipoint_evaluation(self, points: &[T]) -> Vec<T> {
431        let n = points.len();
432        if n <= 32 {
433            return points.iter().map(|p| self.eval(p.clone())).collect();
434        }
435        let mut subproduct_tree = Vec::with_capacity(n * 2);
436        subproduct_tree.resize_with(n, Zero::zero);
437        for x in points {
438            subproduct_tree.push(Self::from_vec(vec![-x.clone(), T::one()]));
439        }
440        for i in (1..n).rev() {
441            subproduct_tree[i] = &subproduct_tree[i * 2] * &subproduct_tree[i * 2 + 1];
442        }
443        let mut uptree_t = Vec::with_capacity(n * 2);
444        uptree_t.resize_with(1, Zero::zero);
445        subproduct_tree.reverse();
446        subproduct_tree.pop();
447        let m = self.length();
448        let v = subproduct_tree.pop().unwrap().reversed().resized(m);
449        let s = C::transform(self.data, m * 2);
450        uptree_t.push(v.inv(m).middle_product(&s, m * 2).resized(n).reversed());
451        for i in 1..n {
452            let subl = subproduct_tree.pop().unwrap();
453            let subr = subproduct_tree.pop().unwrap();
454            let (dl, dr) = (subl.length(), subr.length());
455            let len = dl.max(dr) + uptree_t[i].length();
456            let s = C::transform(uptree_t[i].data.to_vec(), len);
457            uptree_t.push(subr.middle_product(&s, len).prefix(dl));
458            uptree_t.push(subl.middle_product(&s, len).prefix(dr));
459        }
460        uptree_t[n..]
461            .iter()
462            .map(|u| u.data.first().cloned().unwrap_or_else(Zero::zero))
463            .collect()
464    }
465    pub fn product_all<I>(iter: I, deg: usize) -> Self
466    where
467        I: IntoIterator<Item = Self>,
468    {
469        let mut heap: BinaryHeap<_> = iter
470            .into_iter()
471            .map(|f| PartialIgnoredOrd(Reverse(f.length()), f))
472            .collect();
473        while let Some(PartialIgnoredOrd(_, x)) = heap.pop() {
474            if let Some(PartialIgnoredOrd(_, y)) = heap.pop() {
475                let z = (x * y).prefix(deg);
476                heap.push(PartialIgnoredOrd(Reverse(z.length()), z));
477            } else {
478                return x;
479            }
480        }
481        Self::one()
482    }
483    pub fn sum_all_rational<I>(iter: I, deg: usize) -> (Self, Self)
484    where
485        I: IntoIterator<Item = (Self, Self)>,
486    {
487        let mut heap: BinaryHeap<_> = iter
488            .into_iter()
489            .map(|(f, g)| PartialIgnoredOrd(Reverse(f.length().max(g.length())), (f, g)))
490            .collect();
491        while let Some(PartialIgnoredOrd(_, (xa, xb))) = heap.pop() {
492            if let Some(PartialIgnoredOrd(_, (ya, yb))) = heap.pop() {
493                let zb = (&xb * &yb).prefix(deg);
494                let za = (xa * yb + ya * xb).prefix(deg);
495                heap.push(PartialIgnoredOrd(
496                    Reverse(za.length().max(zb.length())),
497                    (za, zb),
498                ));
499            } else {
500                return (xa, xb);
501            }
502        }
503        (Self::zero(), Self::one())
504    }
505    pub fn kth_term_of_linearly_recurrence(self, a: Vec<T>, k: usize) -> T {
506        if let Some(x) = a.get(k) {
507            return x.clone();
508        }
509        let p = (Self::from_vec(a).prefix(self.length() - 1) * &self).prefix(self.length() - 1);
510        p.bostan_mori(self, k)
511    }
512    pub fn kth_term(a: Vec<T>, k: usize) -> T {
513        if let Some(x) = a.get(k) {
514            return x.clone();
515        }
516        Self::from_vec(berlekamp_massey(&a)).kth_term_of_linearly_recurrence(a, k)
517    }
518    /// sum_i a_i exp(b_i x)
519    pub fn linear_sum_of_exp<I, F>(iter: I, deg: usize, mut inv_fact: F) -> Self
520    where
521        I: IntoIterator<Item = (T, T)>,
522        F: FnMut(usize) -> T,
523    {
524        let (p, q) = Self::sum_all_rational(
525            iter.into_iter()
526                .map(|(a, b)| (Self::from_vec(vec![a]), Self::from_vec(vec![T::one(), -b]))),
527            deg,
528        );
529        let mut f = (p * q.inv(deg)).prefix(deg);
530        for i in 0..f.length() {
531            f[i] *= inv_fact(i);
532        }
533        f
534    }

More examples

Hide additional examples

crates/library_checker/src/polynomial/inv_of_formal_power_series.rs (line 11)

6pub fn inv_of_formal_power_series(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, n, a: [MInt998244353; n]);
10    let f = Fps998244353::from_vec(a);
11    let g = f.inv(n);
12    iter_print!(writer, @it g.data);
13}

crates/competitive/src/math/formal_power_series/formal_power_series_nums.rs (line 220)

211    fn div(mut self, mut rhs: Self) -> Self::Output {
212        self.trim_tail_zeros();
213        rhs.trim_tail_zeros();
214        if self.length() < rhs.length() {
215            return Self::zero();
216        }
217        self.data.reverse();
218        rhs.data.reverse();
219        let n = self.length() - rhs.length() + 1;
220        let mut res = self * rhs.inv(n);
221        res.truncate(n);
222        res.data.reverse();
223        res
224    }

Source

pub fn exp(&self, deg: usize) -> Self

Examples found in repository ?

crates/library_checker/src/polynomial/exp_of_formal_power_series.rs (line 11)

6pub fn exp_of_formal_power_series(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, n, a: [MInt998244353; n]);
10    let f = Fps998244353::from_vec(a);
11    let g = f.exp(n);
12    iter_print!(writer, @it g.data);
13}

More examples

Hide additional examples

crates/competitive/src/math/formal_power_series/formal_power_series_impls.rs (line 306)

278    pub fn pow(&self, rhs: usize, deg: usize) -> Self {
279        if rhs == 0 {
280            return Self::from_vec(
281                once(T::one())
282                    .chain(repeat_with(T::zero))
283                    .take(deg)
284                    .collect(),
285            );
286        }
287        if let Some(k) = self.iter().position(|x| !x.is_zero()) {
288            if k >= (deg + rhs - 1) / rhs {
289                Self::zeros(deg)
290            } else {
291                let mut x0 = self[k].clone();
292                let rev = T::one() / x0.clone();
293                let x = {
294                    let mut x = T::one();
295                    let mut y = rhs;
296                    while y > 0 {
297                        if y & 1 == 1 {
298                            x *= x0.clone();
299                        }
300                        x0 *= x0.clone();
301                        y >>= 1;
302                    }
303                    x
304                };
305                let mut f = (self.clone() * &rev) >> k;
306                f = (f.log(deg) * &T::from(rhs)).exp(deg) * &x;
307                f.truncate(deg - k * rhs);
308                f <<= k * rhs;
309                f
310            }
311        } else {
312            Self::zeros(deg)
313        }
314    }
315}
316
317impl<T, C> FormalPowerSeries<T, C>
318where
319    T: FormalPowerSeriesCoefficientSqrt,
320    C: ConvolveSteps<T = Vec<T>>,
321{
322    pub fn sqrt(&self, deg: usize) -> Option<Self> {
323        if self[0].is_zero() {
324            if let Some(k) = self.iter().position(|x| !x.is_zero()) {
325                if k % 2 != 0 {
326                    return None;
327                } else if deg > k / 2 {
328                    return Some((self >> k).sqrt(deg - k / 2)? << (k / 2));
329                }
330            }
331        } else {
332            let inv2 = T::one() / (T::one() + T::one());
333            let mut f = Self::from(self[0].sqrt_coefficient()?);
334            let mut i = 1;
335            while i < deg {
336                f = (&f + &(self.prefix_ref(i * 2) * f.inv(i * 2))).prefix(i * 2) * &inv2;
337                i *= 2;
338            }
339            f.truncate(deg);
340            return Some(f);
341        }
342        Some(Self::zeros(deg))
343    }
344}
345
346impl<T, C> FormalPowerSeries<T, C>
347where
348    T: FormalPowerSeriesCoefficient,
349    C: ConvolveSteps<T = Vec<T>>,
350{
351    pub fn count_subset_sum<F>(&self, deg: usize, mut inverse: F) -> Self
352    where
353        F: FnMut(usize) -> T,
354    {
355        let n = self.length();
356        let mut f = Self::zeros(n);
357        for i in 1..n {
358            if !self[i].is_zero() {
359                for (j, d) in (0..n).step_by(i).enumerate().skip(1) {
360                    if j & 1 != 0 {
361                        f[d] += self[i].clone() * &inverse(j);
362                    } else {
363                        f[d] -= self[i].clone() * &inverse(j);
364                    }
365                }
366            }
367        }
368        f.exp(deg)
369    }
370    pub fn count_multiset_sum<F>(&self, deg: usize, mut inverse: F) -> Self
371    where
372        F: FnMut(usize) -> T,
373    {
374        let n = self.length();
375        let mut f = Self::zeros(n);
376        for i in 1..n {
377            if !self[i].is_zero() {
378                for (j, d) in (0..n).step_by(i).enumerate().skip(1) {
379                    f[d] += self[i].clone() * &inverse(j);
380                }
381            }
382        }
383        f.exp(deg)
384    }

Source

pub fn log(&self, deg: usize) -> Self

Examples found in repository ?

crates/library_checker/src/polynomial/log_of_formal_power_series.rs (line 11)

6pub fn log_of_formal_power_series(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, n, a: [MInt998244353; n]);
10    let f = Fps998244353::from_vec(a);
11    let g = f.log(n);
12    iter_print!(writer, @it g.data);
13}

More examples

Hide additional examples

crates/competitive/src/math/formal_power_series/formal_power_series_impls.rs (line 265)

260    pub fn exp(&self, deg: usize) -> Self {
261        debug_assert!(self[0].is_zero());
262        let mut f = Self::one();
263        let mut i = 1;
264        while i < deg {
265            let mut g = -f.log(i * 2);
266            g[0] += T::one();
267            for (g, x) in g.iter_mut().zip(self.iter().take(i * 2)) {
268                *g += x.clone();
269            }
270            f = (f * g).prefix(i * 2);
271            i *= 2;
272        }
273        f.prefix(deg)
274    }
275    pub fn log(&self, deg: usize) -> Self {
276        (self.inv(deg) * self.clone().diff()).integral().prefix(deg)
277    }
278    pub fn pow(&self, rhs: usize, deg: usize) -> Self {
279        if rhs == 0 {
280            return Self::from_vec(
281                once(T::one())
282                    .chain(repeat_with(T::zero))
283                    .take(deg)
284                    .collect(),
285            );
286        }
287        if let Some(k) = self.iter().position(|x| !x.is_zero()) {
288            if k >= (deg + rhs - 1) / rhs {
289                Self::zeros(deg)
290            } else {
291                let mut x0 = self[k].clone();
292                let rev = T::one() / x0.clone();
293                let x = {
294                    let mut x = T::one();
295                    let mut y = rhs;
296                    while y > 0 {
297                        if y & 1 == 1 {
298                            x *= x0.clone();
299                        }
300                        x0 *= x0.clone();
301                        y >>= 1;
302                    }
303                    x
304                };
305                let mut f = (self.clone() * &rev) >> k;
306                f = (f.log(deg) * &T::from(rhs)).exp(deg) * &x;
307                f.truncate(deg - k * rhs);
308                f <<= k * rhs;
309                f
310            }
311        } else {
312            Self::zeros(deg)
313        }
314    }

Source

pub fn pow(&self, rhs: usize, deg: usize) -> Self

Examples found in repository ?

crates/library_checker/src/polynomial/pow_of_formal_power_series.rs (line 11)

6pub fn pow_of_formal_power_series(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, n, m, a: [MInt998244353; n]);
10    let f = Fps998244353::from_vec(a);
11    let g = f.pow(m, n);
12    iter_print!(writer, @it g.data);
13}

Source §

impl<T, C> FormalPowerSeries<T, C>
where T: FormalPowerSeriesCoefficientSqrt, C: ConvolveSteps<T = Vec<T>>,

Source

pub fn sqrt(&self, deg: usize) -> Option<Self>

Examples found in repository ?

crates/library_checker/src/polynomial/sqrt_of_formal_power_series.rs (line 11)

6pub fn sqrt_of_formal_power_series(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, n, a: [MInt998244353; n]);
10    let f = Fps998244353::from_vec(a);
11    if let Some(g) = f.sqrt(n) {
12        iter_print!(writer, @it g.data);
13    } else {
14        iter_print!(writer, "-1");
15    }
16}

More examples

Hide additional examples

crates/competitive/src/math/formal_power_series/formal_power_series_impls.rs (line 328)

322    pub fn sqrt(&self, deg: usize) -> Option<Self> {
323        if self[0].is_zero() {
324            if let Some(k) = self.iter().position(|x| !x.is_zero()) {
325                if k % 2 != 0 {
326                    return None;
327                } else if deg > k / 2 {
328                    return Some((self >> k).sqrt(deg - k / 2)? << (k / 2));
329                }
330            }
331        } else {
332            let inv2 = T::one() / (T::one() + T::one());
333            let mut f = Self::from(self[0].sqrt_coefficient()?);
334            let mut i = 1;
335            while i < deg {
336                f = (&f + &(self.prefix_ref(i * 2) * f.inv(i * 2))).prefix(i * 2) * &inv2;
337                i *= 2;
338            }
339            f.truncate(deg);
340            return Some(f);
341        }
342        Some(Self::zeros(deg))
343    }

Source §

impl<T, C> FormalPowerSeries<T, C>
where T: FormalPowerSeriesCoefficient, C: ConvolveSteps<T = Vec<T>>,

Source

pub fn count_subset_sum<F>(&self, deg: usize, inverse: F) -> Self
where F: FnMut(usize) -> T,

Examples found in repository ?

crates/library_checker/src/enumerative_combinatorics/sharp_p_subset_sum.rs (line 18)

9pub fn sharp_p_subset_sum(reader: impl Read, mut writer: impl Write) {
10    let s = read_all_unchecked(reader);
11    let mut scanner = Scanner::new(&s);
12    scan!(scanner, n, t, s: [usize; n]);
13    let f = MemorizedFactorial::new(t);
14    let mut c = vec![MInt998244353::zero(); t + 1];
15    for s in s {
16        c[s] += MInt998244353::one();
17    }
18    let a = Fps998244353::from_vec(c).count_subset_sum(t + 1, |x| f.inv(x));
19    iter_print!(writer, @it a.data[1..]);
20}

Source

pub fn count_multiset_sum<F>(&self, deg: usize, inverse: F) -> Self
where F: FnMut(usize) -> T,

Source

pub fn bostan_mori(self, rhs: Self, n: usize) -> T

[x^n] P(x) / Q(x)

Examples found in repository ?

crates/competitive/src/math/formal_power_series/formal_power_series_impls.rs (line 510)

505    pub fn kth_term_of_linearly_recurrence(self, a: Vec<T>, k: usize) -> T {
506        if let Some(x) = a.get(k) {
507            return x.clone();
508        }
509        let p = (Self::from_vec(a).prefix(self.length() - 1) * &self).prefix(self.length() - 1);
510        p.bostan_mori(self, k)
511    }

Source

pub fn bostan_mori_msb(self, n: usize) -> Self

return F(x) where [x^n] P(x) / Q(x) = [x^d-1] P(x) F(x)

Examples found in repository ?

crates/competitive/src/math/formal_power_series/formal_power_series_impls.rs (line 406)

399    pub fn bostan_mori_msb(self, n: usize) -> Self {
400        let d = self.length() - 1;
401        if n == 0 {
402            return (Self::one() << (d - 1)) / self[0].clone();
403        }
404        let q = self;
405        let mq = q.clone().parity_inversion();
406        let w = (q * &mq).even().bostan_mori_msb(n / 2);
407        let mut s = Self::zeros(w.length() * 2 - (n % 2));
408        for (i, x) in w.iter().enumerate() {
409            s[i * 2 + (1 - n % 2)] = x.clone();
410        }
411        let len = 2 * d + 1;
412        let ts = C::transform(s.prefix(len).data, len);
413        mq.reversed().middle_product(&ts, len).prefix(d + 1)
414    }
415    /// x^n mod self
416    pub fn pow_mod(self, n: usize) -> Self {
417        let d = self.length() - 1;
418        let q = self.reversed();
419        let u = q.clone().bostan_mori_msb(n);
420        let mut f = (u * q).prefix(d).reversed();
421        f.trim_tail_zeros();
422        f
423    }

Source

pub fn pow_mod(self, n: usize) -> Self

x^n mod self

Examples found in repository ?

crates/competitive/src/math/black_box_matrix.rs (line 246)

237    fn apply_pow<C>(&self, mut b: Vec<MInt<M>>, k: usize) -> Vec<MInt<M>>
238    where
239        M: MIntConvert<usize> + MIntConvert<u64>,
240        C: ConvolveSteps<T = Vec<MInt<M>>>,
241    {
242        assert_eq!(self.shape().0, self.shape().1);
243        assert_eq!(self.shape().1, b.len());
244        let n = self.shape().0;
245        let p = self.minimal_polynomial();
246        let f = FormalPowerSeries::<MInt<M>, C>::from_vec(p).pow_mod(k);
247        let mut res = vec![MInt::zero(); n];
248        for f in f {
249            for j in 0..n {
250                res[j] += f * b[j];
251            }
252            b = self.apply(&b);
253        }
254        res
255    }

Source

pub fn multipoint_evaluation(self, points: &[T]) -> Vec<T>

Examples found in repository ?

crates/library_checker/src/polynomial/multipoint_evaluation.rs (line 11)

6pub fn multipoint_evaluation(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, n, m, c: [MInt998244353; n], p: [MInt998244353; m]);
10    let f = Fps998244353::from_vec(c);
11    let res = f.multipoint_evaluation(&p);
12    iter_print!(writer, @it res);
13}

Source

pub fn product_all(iter: I, deg: usize) -> Self
where I: IntoIterator<Item = Self>,

Source

pub fn sum_all_rational(iter: I, deg: usize) -> (Self, Self)
where I: IntoIterator<Item = (Self, Self)>,

Examples found in repository ?

crates/competitive/src/math/formal_power_series/formal_power_series_impls.rs (lines 524-528)

519    pub fn linear_sum_of_exp<I, F>(iter: I, deg: usize, mut inv_fact: F) -> Self
520    where
521        I: IntoIterator<Item = (T, T)>,
522        F: FnMut(usize) -> T,
523    {
524        let (p, q) = Self::sum_all_rational(
525            iter.into_iter()
526                .map(|(a, b)| (Self::from_vec(vec![a]), Self::from_vec(vec![T::one(), -b]))),
527            deg,
528        );
529        let mut f = (p * q.inv(deg)).prefix(deg);
530        for i in 0..f.length() {
531            f[i] *= inv_fact(i);
532        }
533        f
534    }

Source

pub fn kth_term_of_linearly_recurrence(self, a: Vec<T>, k: usize) -> T

Examples found in repository ?

crates/competitive/src/math/formal_power_series/formal_power_series_impls.rs (line 516)

512    pub fn kth_term(a: Vec<T>, k: usize) -> T {
513        if let Some(x) = a.get(k) {
514            return x.clone();
515        }
516        Self::from_vec(berlekamp_massey(&a)).kth_term_of_linearly_recurrence(a, k)
517    }

More examples

Hide additional examples

crates/library_checker/src/other/kth_term_of_linearly_recurrent_sequence.rs (line 14)

9pub fn kth_term_of_linearly_recurrent_sequence(reader: impl Read, mut writer: impl Write) {
10    let s = read_all_unchecked(reader);
11    let mut scanner = Scanner::new(&s);
12    scan!(scanner, d, k, a: [MInt998244353; d], c: [MInt998244353; d]);
13    let q = Fps998244353::one() - (Fps998244353::from_vec(c) << 1);
14    iter_print!(writer, q.kth_term_of_linearly_recurrence(a, k));
15}

Source

pub fn kth_term(a: Vec<T>, k: usize) -> T

Source

pub fn linear_sum_of_exp<I, F>(iter: I, deg: usize, inv_fact: F) -> Self
where I: IntoIterator<Item = (T, T)>, F: FnMut(usize) -> T,

sum_i a_i exp(b_i x)

Source §

impl<M, C> FormalPowerSeries<MInt<M>, C>
where M: MIntConvert<usize>, C: ConvolveSteps<T = Vec<MInt<M>>>,

Source

pub fn taylor_shift(self, a: MInt<M>, f: &MemorizedFactorial<M>) -> Self

f(x) <- f(x + a)

Examples found in repository ?

crates/library_checker/src/polynomial/polynomial_taylor_shift.rs (line 14)

8pub fn polynomial_taylor_shift(reader: impl Read, mut writer: impl Write) {
9    let s = read_all_unchecked(reader);
10    let mut scanner = Scanner::new(&s);
11    scan!(scanner, n, c: MInt998244353, a: [MInt998244353; n]);
12    let f = MemorizedFactorial::new(n);
13    let a = Fps998244353::from_vec(a);
14    let res = a.taylor_shift(c, &f);
15    iter_print!(writer, @it res);
16}

Source §

impl<T, C> FormalPowerSeries<T, C>
where T: FormalPowerSeriesCoefficient, C: ConvolveSteps<T = Vec<T>>,

Source

pub fn div_rem(self, rhs: Self) -> (Self, Self)

Trait Implementations§

Source §

impl<T, C> Add<&FormalPowerSeries<T, C>> for &FormalPowerSeries<T, C>
where T: FormalPowerSeriesCoefficient,

Source §

type Output = FormalPowerSeries<T, C>

The resulting type after applying the + operator.

Source §

fn add(self, rhs: &FormalPowerSeries<T, C>) -> Self::Output

Performs the + operation. Read more

Source §

impl<T, C> Add<&FormalPowerSeries<T, C>> for FormalPowerSeries<T, C>
where T: FormalPowerSeriesCoefficient,

Source §

type Output = FormalPowerSeries<T, C>

The resulting type after applying the + operator.

Source §

fn add(self, rhs: &FormalPowerSeries<T, C>) -> Self::Output

Performs the + operation. Read more

Source §

impl<T, C> Add<&T> for &FormalPowerSeries<T, C>
where T: FormalPowerSeriesCoefficient,

Source §

type Output = FormalPowerSeries<T, C>

The resulting type after applying the + operator.

Source §

fn add(self, rhs: &T) -> Self::Output

Performs the + operation. Read more

Source §

impl<T, C> Add<&T> for FormalPowerSeries<T, C>
where T: FormalPowerSeriesCoefficient,

Source §

type Output = FormalPowerSeries<T, C>

The resulting type after applying the + operator.

Source §

fn add(self, rhs: &T) -> Self::Output

Performs the + operation. Read more

Source §

impl<T, C> Add<FormalPowerSeries<T, C>> for &FormalPowerSeries<T, C>
where T: FormalPowerSeriesCoefficient,

Source §

type Output = FormalPowerSeries<T, C>

The resulting type after applying the + operator.

Source §

fn add(self, rhs: FormalPowerSeries<T, C>) -> Self::Output

Performs the + operation. Read more

Source §

impl<T, C> Add<T> for &FormalPowerSeries<T, C>
where T: FormalPowerSeriesCoefficient,

Source §

type Output = FormalPowerSeries<T, C>

The resulting type after applying the + operator.

Source §

fn add(self, rhs: T) -> Self::Output

Performs the + operation. Read more

Source §

impl<T, C> Add<T> for FormalPowerSeries<T, C>
where T: FormalPowerSeriesCoefficient,

Source §

type Output = FormalPowerSeries<T, C>

The resulting type after applying the + operator.

Source §

fn add(self, rhs: T) -> Self::Output

Performs the + operation. Read more

Source §

impl<T, C> Add for FormalPowerSeries<T, C>
where T: FormalPowerSeriesCoefficient,

Source §

type Output = FormalPowerSeries<T, C>

The resulting type after applying the + operator.

Source §

fn add(self, rhs: Self) -> Self::Output

Performs the + operation. Read more

Source §

impl<T, C> AddAssign<&FormalPowerSeries<T, C>> for FormalPowerSeries<T, C>
where T: FormalPowerSeriesCoefficient,

Source §

fn add_assign(&mut self, rhs: &Self)

Performs the += operation. Read more

Source §

impl<T, C> AddAssign<&T> for FormalPowerSeries<T, C>
where T: FormalPowerSeriesCoefficient,

Source §

fn add_assign(&mut self, rhs: &T)

Performs the += operation. Read more

Source §

impl<T, C> AddAssign<T> for FormalPowerSeries<T, C>
where T: FormalPowerSeriesCoefficient,

Source §

fn add_assign(&mut self, rhs: T)

Performs the += operation. Read more

Source §

impl<T, C> AddAssign for FormalPowerSeries<T, C>
where T: FormalPowerSeriesCoefficient,

Source §

fn add_assign(&mut self, rhs: Self)

Performs the += operation. Read more

Source §

impl<T, C> Clone for FormalPowerSeries<T, C>
where T: Clone,

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<T, C> Debug for FormalPowerSeries<T, C>
where T: Debug,

Source §

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter. Read more

Source §

impl<T: Default, C: Default> Default for FormalPowerSeries<T, C>

Source §

fn default() -> FormalPowerSeries<T, C>

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

Source §

impl<T, C> Div<&FormalPowerSeries<T, C>> for &FormalPowerSeries<T, C>
where T: FormalPowerSeriesCoefficient, C: ConvolveSteps<T = Vec<T>>,

Source §

type Output = FormalPowerSeries<T, C>

The resulting type after applying the / operator.

Source §

fn div(self, rhs: &FormalPowerSeries<T, C>) -> Self::Output

Performs the / operation. Read more

Source §

impl<T, C> Div<&FormalPowerSeries<T, C>> for FormalPowerSeries<T, C>
where T: FormalPowerSeriesCoefficient, C: ConvolveSteps<T = Vec<T>>,

Source §

type Output = FormalPowerSeries<T, C>

The resulting type after applying the / operator.

Source §

fn div(self, rhs: &FormalPowerSeries<T, C>) -> Self::Output

Performs the / operation. Read more

Source §

impl<T, C> Div<&T> for &FormalPowerSeries<T, C>
where T: FormalPowerSeriesCoefficient,

Source §

type Output = FormalPowerSeries<T, C>

The resulting type after applying the / operator.

Source §

fn div(self, rhs: &T) -> Self::Output

Performs the / operation. Read more

Source §

impl<T, C> Div<&T> for FormalPowerSeries<T, C>
where T: FormalPowerSeriesCoefficient,

Source §

type Output = FormalPowerSeries<T, C>

The resulting type after applying the / operator.

Source §

fn div(self, rhs: &T) -> Self::Output

Performs the / operation. Read more

Source §

impl<T, C> Div<FormalPowerSeries<T, C>> for &FormalPowerSeries<T, C>
where T: FormalPowerSeriesCoefficient, C: ConvolveSteps<T = Vec<T>>,

Source §

type Output = FormalPowerSeries<T, C>

The resulting type after applying the / operator.

Source §

fn div(self, rhs: FormalPowerSeries<T, C>) -> Self::Output

Performs the / operation. Read more

Source §

impl<T, C> Div<T> for &FormalPowerSeries<T, C>
where T: FormalPowerSeriesCoefficient,

Source §

type Output = FormalPowerSeries<T, C>

The resulting type after applying the / operator.

Source §

fn div(self, rhs: T) -> Self::Output

Performs the / operation. Read more

Source §

impl<T, C> Div<T> for FormalPowerSeries<T, C>
where T: FormalPowerSeriesCoefficient,

Source §

type Output = FormalPowerSeries<T, C>

The resulting type after applying the / operator.

Source §

fn div(self, rhs: T) -> Self::Output

Performs the / operation. Read more

Source §

impl<T, C> Div for FormalPowerSeries<T, C>
where T: FormalPowerSeriesCoefficient, C: ConvolveSteps<T = Vec<T>>,

Source §

type Output = FormalPowerSeries<T, C>

The resulting type after applying the / operator.

Source §

fn div(self, rhs: Self) -> Self::Output

Performs the / operation. Read more

Source §

impl<T, C> DivAssign<&FormalPowerSeries<T, C>> for FormalPowerSeries<T, C>
where T: FormalPowerSeriesCoefficient, C: ConvolveSteps<T = Vec<T>>,

Source §

fn div_assign(&mut self, rhs: &Self)

Performs the /= operation. Read more

Source §

impl<T, C> DivAssign<&T> for FormalPowerSeries<T, C>
where T: FormalPowerSeriesCoefficient,

Source §

fn div_assign(&mut self, rhs: &T)

Performs the /= operation. Read more

Source §

impl<T, C> DivAssign<T> for FormalPowerSeries<T, C>
where T: FormalPowerSeriesCoefficient,

Source §

fn div_assign(&mut self, rhs: T)

Performs the /= operation. Read more

Source §

impl<T, C> DivAssign for FormalPowerSeries<T, C>
where T: FormalPowerSeriesCoefficient, C: ConvolveSteps<T = Vec<T>>,

Source §

fn div_assign(&mut self, rhs: Self)

Performs the /= operation. Read more

Source §

impl<T, C> From<T> for FormalPowerSeries<T, C>

Source §

fn from(x: T) -> Self

Converts to this type from the input type.

Source §

impl<T, C> From<Vec<T>> for FormalPowerSeries<T, C>

Source §

fn from(data: Vec<T>) -> Self

Converts to this type from the input type.

Source §

impl<T, C> FromIterator<T> for FormalPowerSeries<T, C>

Source §

fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self

Creates a value from an iterator. Read more

Source §

impl<T, C> Index<usize> for FormalPowerSeries<T, C>

Source §

type Output = T

The returned type after indexing.

Source §

fn index(&self, index: usize) -> &Self::Output

Performs the indexing (container[index]) operation. Read more

Source §

impl<T, C> IndexMut<usize> for FormalPowerSeries<T, C>

Source §

fn index_mut(&mut self, index: usize) -> &mut Self::Output

Performs the mutable indexing (container[index]) operation. Read more

Source §

impl<'a, T, C> IntoIterator for &'a FormalPowerSeries<T, C>

Source §

type Item = &'a T

The type of the elements being iterated over.

Source §

type IntoIter = Iter<'a, T>

Which kind of iterator are we turning this into?

Source §

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value. Read more

Source §

impl<'a, T, C> IntoIterator for &'a mut FormalPowerSeries<T, C>

Source §

type Item = &'a mut T

The type of the elements being iterated over.

Source §

type IntoIter = IterMut<'a, T>

Which kind of iterator are we turning this into?

Source §

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value. Read more

Source §

impl<T, C> IntoIterator for FormalPowerSeries<T, C>

Source §

type Item = T

The type of the elements being iterated over.

Source §

type IntoIter = IntoIter<T>

Which kind of iterator are we turning this into?

Source §

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value. Read more

Source §

impl<T, C> Mul<&FormalPowerSeries<T, C>> for &FormalPowerSeries<T, C>
where T: FormalPowerSeriesCoefficient, C: ConvolveSteps<T = Vec<T>>,

Source §

type Output = FormalPowerSeries<T, C>

The resulting type after applying the * operator.

Source §

fn mul(self, rhs: &FormalPowerSeries<T, C>) -> Self::Output

Performs the * operation. Read more

Source §

impl<T, C> Mul<&FormalPowerSeries<T, C>> for FormalPowerSeries<T, C>
where T: FormalPowerSeriesCoefficient, C: ConvolveSteps<T = Vec<T>>,

Source §

type Output = FormalPowerSeries<T, C>

The resulting type after applying the * operator.

Source §

fn mul(self, rhs: &FormalPowerSeries<T, C>) -> Self::Output

Performs the * operation. Read more

Source §

impl<T, C> Mul<&T> for &FormalPowerSeries<T, C>
where T: FormalPowerSeriesCoefficient,

Source §

type Output = FormalPowerSeries<T, C>

The resulting type after applying the * operator.

Source §

fn mul(self, rhs: &T) -> Self::Output

Performs the * operation. Read more

Source §

impl<T, C> Mul<&T> for FormalPowerSeries<T, C>
where T: FormalPowerSeriesCoefficient,

Source §

type Output = FormalPowerSeries<T, C>

The resulting type after applying the * operator.

Source §

fn mul(self, rhs: &T) -> Self::Output

Performs the * operation. Read more

Source §

impl<T, C> Mul<FormalPowerSeries<T, C>> for &FormalPowerSeries<T, C>
where T: FormalPowerSeriesCoefficient, C: ConvolveSteps<T = Vec<T>>,

Source §

type Output = FormalPowerSeries<T, C>

The resulting type after applying the * operator.

Source §

fn mul(self, rhs: FormalPowerSeries<T, C>) -> Self::Output

Performs the * operation. Read more

Source §

impl<T, C> Mul<T> for &FormalPowerSeries<T, C>
where T: FormalPowerSeriesCoefficient,

Source §

type Output = FormalPowerSeries<T, C>

The resulting type after applying the * operator.

Source §

fn mul(self, rhs: T) -> Self::Output

Performs the * operation. Read more

Source §

impl<T, C> Mul<T> for FormalPowerSeries<T, C>
where T: FormalPowerSeriesCoefficient,

Source §

type Output = FormalPowerSeries<T, C>

The resulting type after applying the * operator.

Source §

fn mul(self, rhs: T) -> Self::Output

Performs the * operation. Read more

Source §

impl<T, C> Mul for FormalPowerSeries<T, C>
where C: ConvolveSteps<T = Vec<T>>,

Source §

type Output = FormalPowerSeries<T, C>

The resulting type after applying the * operator.

Source §

fn mul(self, rhs: Self) -> Self::Output

Performs the * operation. Read more

Source §

impl<T, C> MulAssign<&FormalPowerSeries<T, C>> for FormalPowerSeries<T, C>
where T: FormalPowerSeriesCoefficient, C: ConvolveSteps<T = Vec<T>>,

Source §

fn mul_assign(&mut self, rhs: &Self)

Performs the *= operation. Read more

Source §

impl<T, C> MulAssign<&T> for FormalPowerSeries<T, C>
where T: FormalPowerSeriesCoefficient,

Source §

fn mul_assign(&mut self, rhs: &T)

Performs the *= operation. Read more

Source §

impl<T, C> MulAssign<T> for FormalPowerSeries<T, C>
where T: FormalPowerSeriesCoefficient,

Source §

fn mul_assign(&mut self, rhs: T)

Performs the *= operation. Read more

Source §

impl<T, C> MulAssign for FormalPowerSeries<T, C>
where T: FormalPowerSeriesCoefficient, C: ConvolveSteps<T = Vec<T>>,

Source §

fn mul_assign(&mut self, rhs: Self)

Performs the *= operation. Read more

Source §

impl<T, C> Neg for &FormalPowerSeries<T, C>
where T: FormalPowerSeriesCoefficient,

Source §

type Output = FormalPowerSeries<T, C>

The resulting type after applying the - operator.

Source §

fn neg(self) -> Self::Output

Performs the unary - operation. Read more

Source §

impl<T, C> Neg for FormalPowerSeries<T, C>
where T: FormalPowerSeriesCoefficient,

Source §

type Output = FormalPowerSeries<T, C>

The resulting type after applying the - operator.

Source §

fn neg(self) -> Self::Output

Performs the unary - operation. Read more

Source §

fn eq(&self, other: &Self) -> bool

Tests for self and other values to be equal, and is used by ==.

1.0.0 · Source§

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

Source §

impl<T, C> Rem<&FormalPowerSeries<T, C>> for &FormalPowerSeries<T, C>
where T: FormalPowerSeriesCoefficient, C: ConvolveSteps<T = Vec<T>>,

Source §

type Output = FormalPowerSeries<T, C>

The resulting type after applying the % operator.

Source §

fn rem(self, rhs: &FormalPowerSeries<T, C>) -> Self::Output

Performs the % operation. Read more

Source §

impl<T, C> Rem<&FormalPowerSeries<T, C>> for FormalPowerSeries<T, C>
where T: FormalPowerSeriesCoefficient, C: ConvolveSteps<T = Vec<T>>,

Source §

type Output = FormalPowerSeries<T, C>

The resulting type after applying the % operator.

Source §

fn rem(self, rhs: &FormalPowerSeries<T, C>) -> Self::Output

Performs the % operation. Read more

Source §

impl<T, C> Rem<FormalPowerSeries<T, C>> for &FormalPowerSeries<T, C>
where T: FormalPowerSeriesCoefficient, C: ConvolveSteps<T = Vec<T>>,

Source §

type Output = FormalPowerSeries<T, C>

The resulting type after applying the % operator.

Source §

fn rem(self, rhs: FormalPowerSeries<T, C>) -> Self::Output

Performs the % operation. Read more

Source §

impl<T, C> Rem for FormalPowerSeries<T, C>
where T: FormalPowerSeriesCoefficient, C: ConvolveSteps<T = Vec<T>>,

Source §

type Output = FormalPowerSeries<T, C>

The resulting type after applying the % operator.

Source §

fn rem(self, rhs: Self) -> Self::Output

Performs the % operation. Read more

Source §

impl<T, C> RemAssign<&FormalPowerSeries<T, C>> for FormalPowerSeries<T, C>
where T: FormalPowerSeriesCoefficient, C: ConvolveSteps<T = Vec<T>>,

Source §

fn rem_assign(&mut self, rhs: &Self)

Performs the %= operation. Read more

Source §

impl<T, C> RemAssign for FormalPowerSeries<T, C>
where T: FormalPowerSeriesCoefficient, C: ConvolveSteps<T = Vec<T>>,

Source §

fn rem_assign(&mut self, rhs: Self)

Performs the %= operation. Read more

Source §

impl<T, C> Shl<usize> for &FormalPowerSeries<T, C>
where T: FormalPowerSeriesCoefficient,

Source §

type Output = FormalPowerSeries<T, C>

The resulting type after applying the << operator.

Source §

fn shl(self, rhs: usize) -> Self::Output

Performs the << operation. Read more

Source §

impl<T, C> Shl<usize> for FormalPowerSeries<T, C>
where T: FormalPowerSeriesCoefficient,

Source §

type Output = FormalPowerSeries<T, C>

The resulting type after applying the << operator.

Source §

fn shl(self, rhs: usize) -> Self::Output

Performs the << operation. Read more

Source §

impl<T, C> ShlAssign<usize> for FormalPowerSeries<T, C>
where T: FormalPowerSeriesCoefficient,

Source §

fn shl_assign(&mut self, rhs: usize)

Performs the <<= operation. Read more

Source §

impl<T, C> Shr<usize> for &FormalPowerSeries<T, C>
where T: FormalPowerSeriesCoefficient,

Source §

type Output = FormalPowerSeries<T, C>

The resulting type after applying the >> operator.

Source §

fn shr(self, rhs: usize) -> Self::Output

Performs the >> operation. Read more

Source §

impl<T, C> Shr<usize> for FormalPowerSeries<T, C>
where T: FormalPowerSeriesCoefficient,

Source §

type Output = FormalPowerSeries<T, C>

The resulting type after applying the >> operator.

Source §

fn shr(self, rhs: usize) -> Self::Output

Performs the >> operation. Read more

Source §

impl<T, C> ShrAssign<usize> for FormalPowerSeries<T, C>
where T: FormalPowerSeriesCoefficient,

Source §

fn shr_assign(&mut self, rhs: usize)

Performs the >>= operation. Read more

Source §

impl<T, C> Sub<&FormalPowerSeries<T, C>> for &FormalPowerSeries<T, C>
where T: FormalPowerSeriesCoefficient,

Source §

type Output = FormalPowerSeries<T, C>

The resulting type after applying the - operator.

Source §

fn sub(self, rhs: &FormalPowerSeries<T, C>) -> Self::Output

Performs the - operation. Read more

Source §

impl<T, C> Sub<&FormalPowerSeries<T, C>> for FormalPowerSeries<T, C>
where T: FormalPowerSeriesCoefficient,

Source §

type Output = FormalPowerSeries<T, C>

The resulting type after applying the - operator.

Source §

fn sub(self, rhs: &FormalPowerSeries<T, C>) -> Self::Output

Performs the - operation. Read more

Source §

impl<T, C> Sub<&T> for &FormalPowerSeries<T, C>
where T: FormalPowerSeriesCoefficient,

Source §

type Output = FormalPowerSeries<T, C>

The resulting type after applying the - operator.

Source §

fn sub(self, rhs: &T) -> Self::Output

Performs the - operation. Read more

Source §

impl<T, C> Sub<&T> for FormalPowerSeries<T, C>
where T: FormalPowerSeriesCoefficient,

Source §

type Output = FormalPowerSeries<T, C>

The resulting type after applying the - operator.

Source §

fn sub(self, rhs: &T) -> Self::Output

Performs the - operation. Read more

Source §

impl<T, C> Sub<FormalPowerSeries<T, C>> for &FormalPowerSeries<T, C>
where T: FormalPowerSeriesCoefficient,

Source §

type Output = FormalPowerSeries<T, C>

The resulting type after applying the - operator.

Source §

fn sub(self, rhs: FormalPowerSeries<T, C>) -> Self::Output

Performs the - operation. Read more

Source §

impl<T, C> Sub<T> for &FormalPowerSeries<T, C>
where T: FormalPowerSeriesCoefficient,

Source §

type Output = FormalPowerSeries<T, C>

The resulting type after applying the - operator.

Source §

fn sub(self, rhs: T) -> Self::Output

Performs the - operation. Read more

Source §

impl<T, C> Sub<T> for FormalPowerSeries<T, C>
where T: FormalPowerSeriesCoefficient,

Source §

type Output = FormalPowerSeries<T, C>

The resulting type after applying the - operator.

Source §

fn sub(self, rhs: T) -> Self::Output

Performs the - operation. Read more

Source §

impl<T, C> Sub for FormalPowerSeries<T, C>
where T: FormalPowerSeriesCoefficient,

Source §

type Output = FormalPowerSeries<T, C>

The resulting type after applying the - operator.

Source §

fn sub(self, rhs: Self) -> Self::Output

Performs the - operation. Read more

Source §

impl<T, C> SubAssign<&FormalPowerSeries<T, C>> for FormalPowerSeries<T, C>
where T: FormalPowerSeriesCoefficient,

Source §

fn sub_assign(&mut self, rhs: &Self)

Performs the -= operation. Read more

Source §

impl<T, C> SubAssign<&T> for FormalPowerSeries<T, C>
where T: FormalPowerSeriesCoefficient,

Source §

fn sub_assign(&mut self, rhs: &T)

Performs the -= operation. Read more

Source §

impl<T, C> SubAssign<T> for FormalPowerSeries<T, C>
where T: FormalPowerSeriesCoefficient,

Source §

fn sub_assign(&mut self, rhs: T)

Performs the -= operation. Read more

Source §

impl<T, C> SubAssign for FormalPowerSeries<T, C>
where T: FormalPowerSeriesCoefficient,

Source §

fn sub_assign(&mut self, rhs: Self)

Performs the -= operation. Read more

Source §

impl<T, C> Zero for FormalPowerSeries<T, C>
where T: PartialEq,

Source §

fn zero() -> Self

Source §

fn is_zero(&self) -> bool
where Self: PartialEq,

Source §

fn set_zero(&mut self)

Source §

impl<T, C> Eq for FormalPowerSeries<T, C>
where T: PartialEq,

Auto Trait Implementations§

§

impl<T, C> Freeze for FormalPowerSeries<T, C>

§

impl<T, C> RefUnwindSafe for FormalPowerSeries<T, C>
where C: RefUnwindSafe, T: RefUnwindSafe,

§

impl<T, C> Send for FormalPowerSeries<T, C>
where C: Send, T: Send,

§

impl<T, C> Sync for FormalPowerSeries<T, C>
where C: Sync, T: Sync,

§

impl<T, C> Unpin for FormalPowerSeries<T, C>
where C: Unpin, T: Unpin,

§

impl<T, C> UnwindSafe for FormalPowerSeries<T, C>
where C: UnwindSafe, T: 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<!> for T

Source §

fn from(t: !) -> T

Converts to this type from the input type.

Source §

impl<T> From<T> for T

Source §

fn from(t: T) -> T

Returns the argument unchanged.

Source §

impl<T, U> Into 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> 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 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>::Error>

Performs the conversion.

Source §

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

Source §

type Error = >::Error

The type returned in the event of a conversion error.

Source §

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

Performs the conversion.

Struct FormalPowerSeries Copy item path

Fields§

Implementations§

impl<T, C> FormalPowerSeries<T, C>

pub fn from_vec(data: Vec<T>) -> Self

pub fn length(&self) -> usize

pub fn truncate(&mut self, deg: usize)

pub fn iter(&self) -> Iter<'_, T>

pub fn iter_mut(&mut self) -> IterMut<'_, T>

impl<T, C> FormalPowerSeries<T, C>where T: Zero,

pub fn zeros(deg: usize) -> Self

pub fn resize(&mut self, deg: usize)

pub fn resized(self, deg: usize) -> Self

pub fn reversed(self) -> Self

impl<T, C> FormalPowerSeries<T, C>where T: Zero + PartialEq,

pub fn trim_tail_zeros(&mut self)

impl<T, C> FormalPowerSeries<T, C>where T: FormalPowerSeriesCoefficient,

pub fn prefix_ref(&self, deg: usize) -> Self

pub fn prefix(self, deg: usize) -> Self

pub fn even(self) -> Self

pub fn odd(self) -> Self

pub fn diff(self) -> Self

pub fn integral(self) -> Self

pub fn parity_inversion(self) -> Self

pub fn eval(&self, x: T) -> T

impl<T, C> FormalPowerSeries<T, C>where T: FormalPowerSeriesCoefficient, C: ConvolveSteps<T = Vec<T>>,

pub fn inv(&self, deg: usize) -> Self

pub fn exp(&self, deg: usize) -> Self

pub fn log(&self, deg: usize) -> Self

pub fn pow(&self, rhs: usize, deg: usize) -> Self

impl<T, C> FormalPowerSeries<T, C>where T: FormalPowerSeriesCoefficientSqrt, C: ConvolveSteps<T = Vec<T>>,

pub fn sqrt(&self, deg: usize) -> Option<Self>

impl<T, C> FormalPowerSeries<T, C>where T: FormalPowerSeriesCoefficient, C: ConvolveSteps<T = Vec<T>>,

pub fn count_subset_sum<F>(&self, deg: usize, inverse: F) -> Selfwhere F: FnMut(usize) -> T,

pub fn count_multiset_sum<F>(&self, deg: usize, inverse: F) -> Selfwhere F: FnMut(usize) -> T,

pub fn bostan_mori(self, rhs: Self, n: usize) -> T

pub fn bostan_mori_msb(self, n: usize) -> Self

pub fn pow_mod(self, n: usize) -> Self

pub fn multipoint_evaluation(self, points: &[T]) -> Vec<T>

pub fn product_all<I>(iter: I, deg: usize) -> Selfwhere I: IntoIterator<Item = Self>,

pub fn sum_all_rational<I>(iter: I, deg: usize) -> (Self, Self)where I: IntoIterator<Item = (Self, Self)>,

pub fn kth_term_of_linearly_recurrence(self, a: Vec<T>, k: usize) -> T

pub fn kth_term(a: Vec<T>, k: usize) -> T

pub fn linear_sum_of_exp<I, F>(iter: I, deg: usize, inv_fact: F) -> Selfwhere I: IntoIterator<Item = (T, T)>, F: FnMut(usize) -> T,

impl<M, C> FormalPowerSeries<MInt<M>, C>where M: MIntConvert<usize>, C: ConvolveSteps<T = Vec<MInt<M>>>,

pub fn taylor_shift(self, a: MInt<M>, f: &MemorizedFactorial<M>) -> Self

impl<T, C> FormalPowerSeries<T, C>where T: FormalPowerSeriesCoefficient, C: ConvolveSteps<T = Vec<T>>,

pub fn div_rem(self, rhs: Self) -> (Self, Self)

Trait Implementations§

impl<T, C> Add<&FormalPowerSeries<T, C>> for &FormalPowerSeries<T, C>where T: FormalPowerSeriesCoefficient,

type Output = FormalPowerSeries<T, C>

fn add(self, rhs: &FormalPowerSeries<T, C>) -> Self::Output

impl<T, C> Add<&FormalPowerSeries<T, C>> for FormalPowerSeries<T, C>where T: FormalPowerSeriesCoefficient,

type Output = FormalPowerSeries<T, C>

fn add(self, rhs: &FormalPowerSeries<T, C>) -> Self::Output

impl<T, C> Add<&T> for &FormalPowerSeries<T, C>where T: FormalPowerSeriesCoefficient,

type Output = FormalPowerSeries<T, C>

fn add(self, rhs: &T) -> Self::Output

impl<T, C> Add<&T> for FormalPowerSeries<T, C>where T: FormalPowerSeriesCoefficient,

type Output = FormalPowerSeries<T, C>

fn add(self, rhs: &T) -> Self::Output

impl<T, C> Add<FormalPowerSeries<T, C>> for &FormalPowerSeries<T, C>where T: FormalPowerSeriesCoefficient,

type Output = FormalPowerSeries<T, C>

fn add(self, rhs: FormalPowerSeries<T, C>) -> Self::Output

impl<T, C> Add<T> for &FormalPowerSeries<T, C>where T: FormalPowerSeriesCoefficient,

type Output = FormalPowerSeries<T, C>

fn add(self, rhs: T) -> Self::Output

impl<T, C> Add<T> for FormalPowerSeries<T, C>where T: FormalPowerSeriesCoefficient,

type Output = FormalPowerSeries<T, C>

fn add(self, rhs: T) -> Self::Output

impl<T, C> Add for FormalPowerSeries<T, C>where T: FormalPowerSeriesCoefficient,

type Output = FormalPowerSeries<T, C>

fn add(self, rhs: Self) -> Self::Output

impl<T, C> AddAssign<&FormalPowerSeries<T, C>> for FormalPowerSeries<T, C>where T: FormalPowerSeriesCoefficient,

fn add_assign(&mut self, rhs: &Self)

impl<T, C> AddAssign<&T> for FormalPowerSeries<T, C>where T: FormalPowerSeriesCoefficient,

fn add_assign(&mut self, rhs: &T)

impl<T, C> AddAssign<T> for FormalPowerSeries<T, C>where T: FormalPowerSeriesCoefficient,

fn add_assign(&mut self, rhs: T)

impl<T, C> AddAssign for FormalPowerSeries<T, C>where T: FormalPowerSeriesCoefficient,

Struct FormalPowerSeries

impl<T, C> FormalPowerSeries<T, C>
where T: Zero,

impl<T, C> FormalPowerSeries<T, C>
where T: Zero + PartialEq,

impl<T, C> FormalPowerSeries<T, C>
where T: FormalPowerSeriesCoefficient,

impl<T, C> FormalPowerSeries<T, C>
where T: FormalPowerSeriesCoefficient, C: ConvolveSteps<T = Vec<T>>,

impl<T, C> FormalPowerSeries<T, C>
where T: FormalPowerSeriesCoefficientSqrt, C: ConvolveSteps<T = Vec<T>>,

impl<T, C> FormalPowerSeries<T, C>
where T: FormalPowerSeriesCoefficient, C: ConvolveSteps<T = Vec<T>>,

pub fn count_subset_sum<F>(&self, deg: usize, inverse: F) -> Self
where F: FnMut(usize) -> T,

pub fn count_multiset_sum<F>(&self, deg: usize, inverse: F) -> Self
where F: FnMut(usize) -> T,

pub fn product_all<I>(iter: I, deg: usize) -> Self
where I: IntoIterator<Item = Self>,

pub fn sum_all_rational<I>(iter: I, deg: usize) -> (Self, Self)
where I: IntoIterator<Item = (Self, Self)>,

pub fn linear_sum_of_exp<I, F>(iter: I, deg: usize, inv_fact: F) -> Self
where I: IntoIterator<Item = (T, T)>, F: FnMut(usize) -> T,

impl<M, C> FormalPowerSeries<MInt<M>, C>
where M: MIntConvert<usize>, C: ConvolveSteps<T = Vec<MInt<M>>>,

impl<T, C> FormalPowerSeries<T, C>
where T: FormalPowerSeriesCoefficient, C: ConvolveSteps<T = Vec<T>>,

impl<T, C> Add<&FormalPowerSeries<T, C>> for &FormalPowerSeries<T, C>
where T: FormalPowerSeriesCoefficient,

impl<T, C> Add<&FormalPowerSeries<T, C>> for FormalPowerSeries<T, C>
where T: FormalPowerSeriesCoefficient,

impl<T, C> Add<&T> for &FormalPowerSeries<T, C>
where T: FormalPowerSeriesCoefficient,

impl<T, C> Add<&T> for FormalPowerSeries<T, C>
where T: FormalPowerSeriesCoefficient,

impl<T, C> Add<FormalPowerSeries<T, C>> for &FormalPowerSeries<T, C>
where T: FormalPowerSeriesCoefficient,

impl<T, C> Add<T> for &FormalPowerSeries<T, C>
where T: FormalPowerSeriesCoefficient,

impl<T, C> Add<T> for FormalPowerSeries<T, C>
where T: FormalPowerSeriesCoefficient,

impl<T, C> Add for FormalPowerSeries<T, C>
where T: FormalPowerSeriesCoefficient,

impl<T, C> AddAssign<&FormalPowerSeries<T, C>> for FormalPowerSeries<T, C>
where T: FormalPowerSeriesCoefficient,

impl<T, C> AddAssign<&T> for FormalPowerSeries<T, C>
where T: FormalPowerSeriesCoefficient,

impl<T, C> AddAssign<T> for FormalPowerSeries<T, C>
where T: FormalPowerSeriesCoefficient,

impl<T, C> AddAssign for FormalPowerSeries<T, C>
where T: FormalPowerSeriesCoefficient,

impl<T, C> Clone for FormalPowerSeries<T, C>
where T: Clone,

impl<T, C> Debug for FormalPowerSeries<T, C>
where T: Debug,

impl<T, C> Div<&FormalPowerSeries<T, C>> for &FormalPowerSeries<T, C>
where T: FormalPowerSeriesCoefficient, C: ConvolveSteps<T = Vec<T>>,

impl<T, C> Div<&FormalPowerSeries<T, C>> for FormalPowerSeries<T, C>
where T: FormalPowerSeriesCoefficient, C: ConvolveSteps<T = Vec<T>>,

impl<T, C> Div<&T> for &FormalPowerSeries<T, C>
where T: FormalPowerSeriesCoefficient,

impl<T, C> Div<&T> for FormalPowerSeries<T, C>
where T: FormalPowerSeriesCoefficient,

impl<T, C> Div<FormalPowerSeries<T, C>> for &FormalPowerSeries<T, C>
where T: FormalPowerSeriesCoefficient, C: ConvolveSteps<T = Vec<T>>,

impl<T, C> Div<T> for &FormalPowerSeries<T, C>
where T: FormalPowerSeriesCoefficient,

impl<T, C> Div<T> for FormalPowerSeries<T, C>
where T: FormalPowerSeriesCoefficient,

impl<T, C> Div for FormalPowerSeries<T, C>
where T: FormalPowerSeriesCoefficient, C: ConvolveSteps<T = Vec<T>>,