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

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

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

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 219)

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

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

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 282)

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

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 418)

400    pub fn multipoint_evaluation(self, points: &[T]) -> Vec<T> {
401        let n = points.len();
402        if n <= 32 {
403            return points.iter().map(|p| self.eval(p.clone())).collect();
404        }
405        let mut subproduct_tree = Vec::with_capacity(n * 2);
406        subproduct_tree.resize_with(n, Zero::zero);
407        for x in points {
408            subproduct_tree.push(Self::from_vec(vec![-x.clone(), T::one()]));
409        }
410        for i in (1..n).rev() {
411            subproduct_tree[i] = &subproduct_tree[i * 2] * &subproduct_tree[i * 2 + 1];
412        }
413        let mut uptree_t = Vec::with_capacity(n * 2);
414        uptree_t.resize_with(1, Zero::zero);
415        subproduct_tree.reverse();
416        subproduct_tree.pop();
417        let m = self.length();
418        let v = subproduct_tree.pop().unwrap().reversed().resized(m);
419        let s = C::transform(self.data, m * 2);
420        uptree_t.push(v.inv(m).middle_product(&s, m * 2).resized(n).reversed());
421        for i in 1..n {
422            let subl = subproduct_tree.pop().unwrap();
423            let subr = subproduct_tree.pop().unwrap();
424            let (dl, dr) = (subl.length(), subr.length());
425            let len = dl.max(dr) + uptree_t[i].length();
426            let s = C::transform(uptree_t[i].data.to_vec(), len);
427            uptree_t.push(subr.middle_product(&s, len).prefix(dl));
428            uptree_t.push(subl.middle_product(&s, len).prefix(dr));
429        }
430        uptree_t[n..]
431            .iter()
432            .map(|u| u.data.first().cloned().unwrap_or_else(Zero::zero))
433            .collect()
434    }

Source

pub fn reversed(self) -> Self

Examples found in repository ?

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

394    fn middle_product(self, other: &C::F, deg: usize) -> Self {
395        let n = self.length();
396        let mut s = C::transform(self.reversed().data, deg);
397        C::multiply(&mut s, other);
398        Self::from_vec((C::inverse_transform(s, deg))[n - 1..].to_vec())
399    }
400    pub fn multipoint_evaluation(self, points: &[T]) -> Vec<T> {
401        let n = points.len();
402        if n <= 32 {
403            return points.iter().map(|p| self.eval(p.clone())).collect();
404        }
405        let mut subproduct_tree = Vec::with_capacity(n * 2);
406        subproduct_tree.resize_with(n, Zero::zero);
407        for x in points {
408            subproduct_tree.push(Self::from_vec(vec![-x.clone(), T::one()]));
409        }
410        for i in (1..n).rev() {
411            subproduct_tree[i] = &subproduct_tree[i * 2] * &subproduct_tree[i * 2 + 1];
412        }
413        let mut uptree_t = Vec::with_capacity(n * 2);
414        uptree_t.resize_with(1, Zero::zero);
415        subproduct_tree.reverse();
416        subproduct_tree.pop();
417        let m = self.length();
418        let v = subproduct_tree.pop().unwrap().reversed().resized(m);
419        let s = C::transform(self.data, m * 2);
420        uptree_t.push(v.inv(m).middle_product(&s, m * 2).resized(n).reversed());
421        for i in 1..n {
422            let subl = subproduct_tree.pop().unwrap();
423            let subr = subproduct_tree.pop().unwrap();
424            let (dl, dr) = (subl.length(), subr.length());
425            let len = dl.max(dr) + uptree_t[i].length();
426            let s = C::transform(uptree_t[i].data.to_vec(), len);
427            uptree_t.push(subr.middle_product(&s, len).prefix(dl));
428            uptree_t.push(subl.middle_product(&s, len).prefix(dr));
429        }
430        uptree_t[n..]
431            .iter()
432            .map(|u| u.data.first().cloned().unwrap_or_else(Zero::zero))
433            .collect()
434    }

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    }

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 237)

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

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 263)

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

Source

pub fn even(self) -> Self

Examples found in repository ?

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

378    pub fn bostan_mori(self, rhs: Self, mut n: usize) -> T {
379        let mut p = self;
380        let mut q = rhs;
381        while n > 0 {
382            let mut mq = q.clone();
383            mq.iter_mut()
384                .skip(1)
385                .step_by(2)
386                .for_each(|x| *x = -x.clone());
387            let u = p * mq.clone();
388            p = if n % 2 == 0 { u.even() } else { u.odd() };
389            q = (q * mq).even();
390            n /= 2;
391        }
392        p[0].clone() / q[0].clone()
393    }

Source

pub fn odd(self) -> Self

Examples found in repository ?

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

378    pub fn bostan_mori(self, rhs: Self, mut n: usize) -> T {
379        let mut p = self;
380        let mut q = rhs;
381        while n > 0 {
382            let mut mq = q.clone();
383            mq.iter_mut()
384                .skip(1)
385                .step_by(2)
386                .for_each(|x| *x = -x.clone());
387            let u = p * mq.clone();
388            p = if n % 2 == 0 { u.even() } else { u.odd() };
389            q = (q * mq).even();
390            n /= 2;
391        }
392        p[0].clone() / q[0].clone()
393    }

Source

pub fn diff(self) -> Self

Examples found in repository ?

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

268    pub fn log(&self, deg: usize) -> Self {
269        (self.inv(deg) * self.clone().diff()).integral().prefix(deg)
270    }

Source

pub fn integral(self) -> Self

Examples found in repository ?

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

268    pub fn log(&self, deg: usize) -> Self {
269        (self.inv(deg) * self.clone().diff()).integral().prefix(deg)
270    }

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 403)

400    pub fn multipoint_evaluation(self, points: &[T]) -> Vec<T> {
401        let n = points.len();
402        if n <= 32 {
403            return points.iter().map(|p| self.eval(p.clone())).collect();
404        }
405        let mut subproduct_tree = Vec::with_capacity(n * 2);
406        subproduct_tree.resize_with(n, Zero::zero);
407        for x in points {
408            subproduct_tree.push(Self::from_vec(vec![-x.clone(), T::one()]));
409        }
410        for i in (1..n).rev() {
411            subproduct_tree[i] = &subproduct_tree[i * 2] * &subproduct_tree[i * 2 + 1];
412        }
413        let mut uptree_t = Vec::with_capacity(n * 2);
414        uptree_t.resize_with(1, Zero::zero);
415        subproduct_tree.reverse();
416        subproduct_tree.pop();
417        let m = self.length();
418        let v = subproduct_tree.pop().unwrap().reversed().resized(m);
419        let s = C::transform(self.data, m * 2);
420        uptree_t.push(v.inv(m).middle_product(&s, m * 2).resized(n).reversed());
421        for i in 1..n {
422            let subl = subproduct_tree.pop().unwrap();
423            let subr = subproduct_tree.pop().unwrap();
424            let (dl, dr) = (subl.length(), subr.length());
425            let len = dl.max(dr) + uptree_t[i].length();
426            let s = C::transform(uptree_t[i].data.to_vec(), len);
427            uptree_t.push(subr.middle_product(&s, len).prefix(dl));
428            uptree_t.push(subl.middle_product(&s, len).prefix(dr));
429        }
430        uptree_t[n..]
431            .iter()
432            .map(|u| u.data.first().cloned().unwrap_or_else(Zero::zero))
433            .collect()
434    }

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 269)

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

More examples

Hide additional examples

crates/library_checker/src/math/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/math/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 299)

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

Source

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

Examples found in repository ?

crates/library_checker/src/math/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 258)

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

Source

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

Examples found in repository ?

crates/library_checker/src/math/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/math/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 321)

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

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/math/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

Examples found in repository ?

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

475    pub fn kth_term_of_linearly_recurrence(self, a: Vec<T>, k: usize) -> T {
476        if let Some(x) = a.get(k) {
477            return x.clone();
478        }
479        let p = (Self::from_vec(a).prefix(self.length() - 1) * &self).prefix(self.length() - 1);
480        p.bostan_mori(self, k)
481    }

Source

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

Examples found in repository ?

crates/library_checker/src/math/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 494-498)

489    pub fn linear_sum_of_exp<I, F>(iter: I, deg: usize, mut inv_fact: F) -> Self
490    where
491        I: IntoIterator<Item = (T, T)>,
492        F: FnMut(usize) -> T,
493    {
494        let (p, q) = Self::sum_all_rational(
495            iter.into_iter()
496                .map(|(a, b)| (Self::from_vec(vec![a]), Self::from_vec(vec![T::one(), -b]))),
497            deg,
498        );
499        let mut f = (p * q.inv(deg)).prefix(deg);
500        for i in 0..f.length() {
501            f[i] *= inv_fact(i);
502        }
503        f
504    }

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 486)

482    pub fn kth_term(a: Vec<T>, k: usize) -> T {
483        if let Some(x) = a.get(k) {
484            return x.clone();
485        }
486        Self::from_vec(berlekamp_massey(&a)).kth_term_of_linearly_recurrence(a, k)
487    }

More examples

Hide additional examples

crates/library_checker/src/math/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/math/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 FormalPowerSeriesCopy 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 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 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,

fn add_assign(&mut self, rhs: Self)

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

fn clone(&self) -> Self

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>>,

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

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

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