Struct FormalPowerSeries

Source

pub struct FormalPowerSeries<T, C> {
    pub data: Vec<T>,
    _marker: PhantomData<C>,
}

Fields§

§data: Vec<T>§_marker: PhantomData<C>

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

More examples

Hide additional examples

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

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

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

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

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

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

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

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

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

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

Additional examples can be found in:

Source

pub fn length(&self) -> usize

Examples found in repository ?

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

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

More examples

Hide additional examples

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

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

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

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

More examples

Hide additional examples

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

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

Source

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

Examples found in repository ?

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

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

More examples

Hide additional examples

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

232    pub fn eval(&self, x: T) -> T {
233        let mut base = T::one();
234        let mut res = T::zero();
235        for a in self.iter() {
236            res += base.clone() * a.clone();
237            base *= x.clone();
238        }
239        res
240    }
241}
242
243impl<T, C> FormalPowerSeries<T, C>
244where
245    T: FormalPowerSeriesCoefficient,
246    C: ConvolveSteps<T = Vec<T>>,
247{
248    pub fn inv(&self, deg: usize) -> Self {
249        debug_assert!(!self[0].is_zero());
250        if self.data.iter().filter(|x| !x.is_zero()).count()
251            <= deg.next_power_of_two().trailing_zeros() as usize * 6
252        {
253            let pos: Vec<_> = self
254                .data
255                .iter()
256                .enumerate()
257                .skip(1)
258                .filter_map(|(i, x)| if x.is_zero() { None } else { Some(i) })
259                .collect();
260            let mut f = Self::zeros(deg);
261            f[0] = T::one() / self[0].clone();
262            for i in 1..deg {
263                let mut tot = T::zero();
264                for &j in &pos {
265                    if j > i {
266                        break;
267                    }
268                    tot += self[j].clone() * &f[i - j];
269                }
270                f[i] = -tot * &f[0];
271            }
272            return f;
273        }
274        let mut f = Self::from(T::one() / self[0].clone());
275        let mut i = 1;
276        while i < deg {
277            let g = self.prefix_ref((i * 2).min(deg));
278            let h = f.clone();
279            let mut g = C::transform(g.data, 2 * i);
280            let h = C::transform(h.data, 2 * i);
281            C::multiply(&mut g, &h);
282            let mut g = Self::from_vec(C::inverse_transform(g, 2 * i));
283            g >>= i;
284            let mut g = C::transform(g.data, 2 * i);
285            C::multiply(&mut g, &h);
286            let g = Self::from_vec(C::inverse_transform(g, 2 * i));
287            f.data.extend((-g).into_iter().take(i));
288            i *= 2;
289        }
290        f.truncate(deg);
291        f
292    }
293    pub fn exp(&self, deg: usize) -> Self {
294        debug_assert!(self[0].is_zero());
295        if self.data.iter().filter(|x| !x.is_zero()).count()
296            <= deg.next_power_of_two().trailing_zeros() as usize * 16
297        {
298            let diff = self.clone().diff();
299            let pos: Vec<_> = diff
300                .data
301                .iter()
302                .enumerate()
303                .filter_map(|(i, x)| if x.is_zero() { None } else { Some(i) })
304                .collect();
305            let mf = T::memorized_factorial(deg);
306            let mut f = Self::zeros(deg);
307            f[0] = T::one();
308            for i in 1..deg {
309                let mut tot = T::zero();
310                for &j in &pos {
311                    if j > i - 1 {
312                        break;
313                    }
314                    tot += f[i - 1 - j].clone() * &diff[j];
315                }
316                f[i] = tot * T::memorized_inv(&mf, i);
317            }
318            return f;
319        }
320        let mut f = Self::one();
321        let mut i = 1;
322        while i < deg {
323            let mut g = -f.log(i * 2);
324            g[0] += T::one();
325            for (g, x) in g.iter_mut().zip(self.iter().take(i * 2)) {
326                *g += x.clone();
327            }
328            f = (f * g).prefix(i * 2);
329            i *= 2;
330        }
331        f.prefix(deg)
332    }
333    pub fn log(&self, deg: usize) -> Self {
334        (self.inv(deg) * self.clone().diff()).integral().prefix(deg)
335    }
336    pub fn pow(&self, rhs: usize, deg: usize) -> Self {
337        if rhs == 0 {
338            return Self::from_vec(
339                once(T::one())
340                    .chain(repeat_with(T::zero))
341                    .take(deg)
342                    .collect(),
343            );
344        }
345        if let Some(k) = self.iter().position(|x| !x.is_zero()) {
346            if k >= deg.div_ceil(rhs) {
347                Self::zeros(deg)
348            } else {
349                let deg = deg - k * rhs;
350                let x0 = self[k].clone();
351                let mut f = (self >> k) / &x0;
352                if f.data.iter().filter(|x| !x.is_zero()).count()
353                    <= deg.next_power_of_two().trailing_zeros() as usize * 12
354                {
355                    f = f.pow_sparse1(T::from(rhs), deg);
356                } else {
357                    f = (f.log(deg) * &T::from(rhs)).exp(deg);
358                }
359                f *= x0.pow(rhs);
360                f <<= k * rhs;
361                f
362            }
363        } else {
364            Self::zeros(deg)
365        }
366    }
367    fn pow_sparse1(&self, rhs: T, deg: usize) -> Self {
368        debug_assert!(!self[0].is_zero());
369        let pos: Vec<_> = self
370            .data
371            .iter()
372            .enumerate()
373            .skip(1)
374            .filter_map(|(i, x)| if x.is_zero() { None } else { Some(i) })
375            .collect();
376        let mf = T::memorized_factorial(deg);
377        let mut f = Self::zeros(deg);
378        f[0] = T::one();
379        for i in 1..deg {
380            let mut tot = T::zero();
381            for &j in &pos {
382                if j > i {
383                    break;
384                }
385                tot += (T::from(j) * &rhs - T::from(i - j)) * &self[j] * &f[i - j];
386            }
387            f[i] = tot * T::memorized_inv(&mf, i);
388        }
389        f
390    }
391}
392
393impl<T, C> FormalPowerSeries<T, C>
394where
395    T: FormalPowerSeriesCoefficientSqrt,
396    C: ConvolveSteps<T = Vec<T>>,
397{
398    pub fn sqrt(&self, deg: usize) -> Option<Self> {
399        if self[0].is_zero() {
400            if let Some(k) = self.iter().position(|x| !x.is_zero()) {
401                if k % 2 != 0 {
402                    return None;
403                } else if deg > k / 2 {
404                    return Some((self >> k).sqrt(deg - k / 2)? << (k / 2));
405                }
406            }
407        } else {
408            let s = self[0].sqrt_coefficient()?;
409            if self.data.iter().filter(|x| !x.is_zero()).count()
410                <= deg.next_power_of_two().trailing_zeros() as usize * 4
411            {
412                let t = self[0].clone();
413                let mut f = self / t;
414                f = f.pow_sparse1(T::from(1) / T::from(2), deg);
415                f *= s;
416                return Some(f);
417            }
418
419            let mut f = Self::from(s);
420            let inv2 = T::one() / (T::one() + T::one());
421            let mut i = 1;
422            while i < deg {
423                f = (&f + &(self.prefix_ref(i * 2) * f.inv(i * 2))).prefix(i * 2) * &inv2;
424                i *= 2;
425            }
426            f.truncate(deg);
427            return Some(f);
428        }
429        Some(Self::zeros(deg))
430    }
431}
432
433impl<T, C> FormalPowerSeries<T, C>
434where
435    T: FormalPowerSeriesCoefficient,
436    C: ConvolveSteps<T = Vec<T>>,
437{
438    pub fn count_subset_sum<F>(&self, deg: usize, mut inverse: F) -> Self
439    where
440        F: FnMut(usize) -> T,
441    {
442        let n = self.length();
443        let mut f = Self::zeros(n);
444        for i in 1..n {
445            if !self[i].is_zero() {
446                for (j, d) in (0..n).step_by(i).enumerate().skip(1) {
447                    if j & 1 != 0 {
448                        f[d] += self[i].clone() * &inverse(j);
449                    } else {
450                        f[d] -= self[i].clone() * &inverse(j);
451                    }
452                }
453            }
454        }
455        f.exp(deg)
456    }
457    pub fn count_multiset_sum<F>(&self, deg: usize, mut inverse: F) -> Self
458    where
459        F: FnMut(usize) -> T,
460    {
461        let n = self.length();
462        let mut f = Self::zeros(n);
463        for i in 1..n {
464            if !self[i].is_zero() {
465                for (j, d) in (0..n).step_by(i).enumerate().skip(1) {
466                    f[d] += self[i].clone() * &inverse(j);
467                }
468            }
469        }
470        f.exp(deg)
471    }
472    /// [x^n] P(x) / Q(x)
473    pub fn bostan_mori(mut self, mut rhs: Self, mut n: usize) -> T
474    where
475        C: NttReuse<T = Vec<T>>,
476    {
477        let mut res = T::zero();
478        rhs.trim_tail_zeros();
479        if self.length() >= rhs.length() {
480            let r = &self / &rhs;
481            if n < r.length() {
482                res = r[n].clone();
483            }
484            self -= r * &rhs;
485            self.trim_tail_zeros();
486        }
487        let k = rhs.length().next_power_of_two();
488        let mut p = C::transform(self.data, k * 2);
489        let mut q = C::transform(rhs.data, k * 2);
490        while n > 0 {
491            let t = C::even_mul_normal_neg(&q, &q);
492            p = if n.is_multiple_of(2) {
493                C::even_mul_normal_neg(&p, &q)
494            } else {
495                C::odd_mul_normal_neg(&p, &q)
496            };
497            q = t;
498            n /= 2;
499            if n != 0 {
500                if C::MULTIPLE {
501                    p = C::transform(C::inverse_transform(p, k), k * 2);
502                    q = C::transform(C::inverse_transform(q, k), k * 2);
503                } else {
504                    p = C::ntt_doubling(p);
505                    q = C::ntt_doubling(q);
506                }
507            }
508        }
509        let p = C::inverse_transform(p, k);
510        let q = C::inverse_transform(q, k);
511        res + p[0].clone() / q[0].clone()
512    }
513    /// return F(x) where [x^n] P(x) / Q(x) = [x^d-1] P(x) F(x)
514    pub fn bostan_mori_msb(self, n: usize) -> Self {
515        let d = self.length() - 1;
516        if n == 0 {
517            return (Self::one() << (d - 1)) / self[0].clone();
518        }
519        let q = self;
520        let mq = q.clone().parity_inversion();
521        let w = (q * &mq).even().bostan_mori_msb(n / 2);
522        let mut s = Self::zeros(w.length() * 2 - (n % 2));
523        for (i, x) in w.iter().enumerate() {
524            s[i * 2 + (1 - n % 2)] = x.clone();
525        }
526        let len = 2 * d + 1;
527        let ts = C::transform(s.prefix(len).data, len);
528        mq.reversed().middle_product(&ts, len).prefix(d + 1)
529    }

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

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

More examples

Hide additional examples

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

196    pub fn diff(mut self) -> Self {
197        let mut c = T::one();
198        for x in self.iter_mut().skip(1) {
199            *x *= &c;
200            c += T::one();
201        }
202        if self.length() > 0 {
203            self.data.remove(0);
204        }
205        self
206    }
207    pub fn integral(mut self) -> Self {
208        let n = self.length();
209        self.data.insert(0, Zero::zero());
210        let mut fact = Vec::with_capacity(n + 1);
211        let mut c = T::one();
212        fact.push(c.clone());
213        for _ in 1..n {
214            fact.push(fact.last().cloned().unwrap() * c.clone());
215            c += T::one();
216        }
217        let mut invf = T::one() / (fact.last().cloned().unwrap() * c.clone());
218        for x in self.iter_mut().skip(1).rev() {
219            *x *= invf.clone() * fact.pop().unwrap();
220            invf *= c.clone();
221            c -= T::one();
222        }
223        self
224    }
225    pub fn parity_inversion(mut self) -> Self {
226        self.iter_mut()
227            .skip(1)
228            .step_by(2)
229            .for_each(|x| *x = -x.clone());
230        self
231    }
232    pub fn eval(&self, x: T) -> T {
233        let mut base = T::one();
234        let mut res = T::zero();
235        for a in self.iter() {
236            res += base.clone() * a.clone();
237            base *= x.clone();
238        }
239        res
240    }
241}
242
243impl<T, C> FormalPowerSeries<T, C>
244where
245    T: FormalPowerSeriesCoefficient,
246    C: ConvolveSteps<T = Vec<T>>,
247{
248    pub fn inv(&self, deg: usize) -> Self {
249        debug_assert!(!self[0].is_zero());
250        if self.data.iter().filter(|x| !x.is_zero()).count()
251            <= deg.next_power_of_two().trailing_zeros() as usize * 6
252        {
253            let pos: Vec<_> = self
254                .data
255                .iter()
256                .enumerate()
257                .skip(1)
258                .filter_map(|(i, x)| if x.is_zero() { None } else { Some(i) })
259                .collect();
260            let mut f = Self::zeros(deg);
261            f[0] = T::one() / self[0].clone();
262            for i in 1..deg {
263                let mut tot = T::zero();
264                for &j in &pos {
265                    if j > i {
266                        break;
267                    }
268                    tot += self[j].clone() * &f[i - j];
269                }
270                f[i] = -tot * &f[0];
271            }
272            return f;
273        }
274        let mut f = Self::from(T::one() / self[0].clone());
275        let mut i = 1;
276        while i < deg {
277            let g = self.prefix_ref((i * 2).min(deg));
278            let h = f.clone();
279            let mut g = C::transform(g.data, 2 * i);
280            let h = C::transform(h.data, 2 * i);
281            C::multiply(&mut g, &h);
282            let mut g = Self::from_vec(C::inverse_transform(g, 2 * i));
283            g >>= i;
284            let mut g = C::transform(g.data, 2 * i);
285            C::multiply(&mut g, &h);
286            let g = Self::from_vec(C::inverse_transform(g, 2 * i));
287            f.data.extend((-g).into_iter().take(i));
288            i *= 2;
289        }
290        f.truncate(deg);
291        f
292    }
293    pub fn exp(&self, deg: usize) -> Self {
294        debug_assert!(self[0].is_zero());
295        if self.data.iter().filter(|x| !x.is_zero()).count()
296            <= deg.next_power_of_two().trailing_zeros() as usize * 16
297        {
298            let diff = self.clone().diff();
299            let pos: Vec<_> = diff
300                .data
301                .iter()
302                .enumerate()
303                .filter_map(|(i, x)| if x.is_zero() { None } else { Some(i) })
304                .collect();
305            let mf = T::memorized_factorial(deg);
306            let mut f = Self::zeros(deg);
307            f[0] = T::one();
308            for i in 1..deg {
309                let mut tot = T::zero();
310                for &j in &pos {
311                    if j > i - 1 {
312                        break;
313                    }
314                    tot += f[i - 1 - j].clone() * &diff[j];
315                }
316                f[i] = tot * T::memorized_inv(&mf, i);
317            }
318            return f;
319        }
320        let mut f = Self::one();
321        let mut i = 1;
322        while i < deg {
323            let mut g = -f.log(i * 2);
324            g[0] += T::one();
325            for (g, x) in g.iter_mut().zip(self.iter().take(i * 2)) {
326                *g += x.clone();
327            }
328            f = (f * g).prefix(i * 2);
329            i *= 2;
330        }
331        f.prefix(deg)
332    }

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

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

More examples

Hide additional examples

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

248    pub fn inv(&self, deg: usize) -> Self {
249        debug_assert!(!self[0].is_zero());
250        if self.data.iter().filter(|x| !x.is_zero()).count()
251            <= deg.next_power_of_two().trailing_zeros() as usize * 6
252        {
253            let pos: Vec<_> = self
254                .data
255                .iter()
256                .enumerate()
257                .skip(1)
258                .filter_map(|(i, x)| if x.is_zero() { None } else { Some(i) })
259                .collect();
260            let mut f = Self::zeros(deg);
261            f[0] = T::one() / self[0].clone();
262            for i in 1..deg {
263                let mut tot = T::zero();
264                for &j in &pos {
265                    if j > i {
266                        break;
267                    }
268                    tot += self[j].clone() * &f[i - j];
269                }
270                f[i] = -tot * &f[0];
271            }
272            return f;
273        }
274        let mut f = Self::from(T::one() / self[0].clone());
275        let mut i = 1;
276        while i < deg {
277            let g = self.prefix_ref((i * 2).min(deg));
278            let h = f.clone();
279            let mut g = C::transform(g.data, 2 * i);
280            let h = C::transform(h.data, 2 * i);
281            C::multiply(&mut g, &h);
282            let mut g = Self::from_vec(C::inverse_transform(g, 2 * i));
283            g >>= i;
284            let mut g = C::transform(g.data, 2 * i);
285            C::multiply(&mut g, &h);
286            let g = Self::from_vec(C::inverse_transform(g, 2 * i));
287            f.data.extend((-g).into_iter().take(i));
288            i *= 2;
289        }
290        f.truncate(deg);
291        f
292    }
293    pub fn exp(&self, deg: usize) -> Self {
294        debug_assert!(self[0].is_zero());
295        if self.data.iter().filter(|x| !x.is_zero()).count()
296            <= deg.next_power_of_two().trailing_zeros() as usize * 16
297        {
298            let diff = self.clone().diff();
299            let pos: Vec<_> = diff
300                .data
301                .iter()
302                .enumerate()
303                .filter_map(|(i, x)| if x.is_zero() { None } else { Some(i) })
304                .collect();
305            let mf = T::memorized_factorial(deg);
306            let mut f = Self::zeros(deg);
307            f[0] = T::one();
308            for i in 1..deg {
309                let mut tot = T::zero();
310                for &j in &pos {
311                    if j > i - 1 {
312                        break;
313                    }
314                    tot += f[i - 1 - j].clone() * &diff[j];
315                }
316                f[i] = tot * T::memorized_inv(&mf, i);
317            }
318            return f;
319        }
320        let mut f = Self::one();
321        let mut i = 1;
322        while i < deg {
323            let mut g = -f.log(i * 2);
324            g[0] += T::one();
325            for (g, x) in g.iter_mut().zip(self.iter().take(i * 2)) {
326                *g += x.clone();
327            }
328            f = (f * g).prefix(i * 2);
329            i *= 2;
330        }
331        f.prefix(deg)
332    }
333    pub fn log(&self, deg: usize) -> Self {
334        (self.inv(deg) * self.clone().diff()).integral().prefix(deg)
335    }
336    pub fn pow(&self, rhs: usize, deg: usize) -> Self {
337        if rhs == 0 {
338            return Self::from_vec(
339                once(T::one())
340                    .chain(repeat_with(T::zero))
341                    .take(deg)
342                    .collect(),
343            );
344        }
345        if let Some(k) = self.iter().position(|x| !x.is_zero()) {
346            if k >= deg.div_ceil(rhs) {
347                Self::zeros(deg)
348            } else {
349                let deg = deg - k * rhs;
350                let x0 = self[k].clone();
351                let mut f = (self >> k) / &x0;
352                if f.data.iter().filter(|x| !x.is_zero()).count()
353                    <= deg.next_power_of_two().trailing_zeros() as usize * 12
354                {
355                    f = f.pow_sparse1(T::from(rhs), deg);
356                } else {
357                    f = (f.log(deg) * &T::from(rhs)).exp(deg);
358                }
359                f *= x0.pow(rhs);
360                f <<= k * rhs;
361                f
362            }
363        } else {
364            Self::zeros(deg)
365        }
366    }
367    fn pow_sparse1(&self, rhs: T, deg: usize) -> Self {
368        debug_assert!(!self[0].is_zero());
369        let pos: Vec<_> = self
370            .data
371            .iter()
372            .enumerate()
373            .skip(1)
374            .filter_map(|(i, x)| if x.is_zero() { None } else { Some(i) })
375            .collect();
376        let mf = T::memorized_factorial(deg);
377        let mut f = Self::zeros(deg);
378        f[0] = T::one();
379        for i in 1..deg {
380            let mut tot = T::zero();
381            for &j in &pos {
382                if j > i {
383                    break;
384                }
385                tot += (T::from(j) * &rhs - T::from(i - j)) * &self[j] * &f[i - j];
386            }
387            f[i] = tot * T::memorized_inv(&mf, i);
388        }
389        f
390    }
391}
392
393impl<T, C> FormalPowerSeries<T, C>
394where
395    T: FormalPowerSeriesCoefficientSqrt,
396    C: ConvolveSteps<T = Vec<T>>,
397{
398    pub fn sqrt(&self, deg: usize) -> Option<Self> {
399        if self[0].is_zero() {
400            if let Some(k) = self.iter().position(|x| !x.is_zero()) {
401                if k % 2 != 0 {
402                    return None;
403                } else if deg > k / 2 {
404                    return Some((self >> k).sqrt(deg - k / 2)? << (k / 2));
405                }
406            }
407        } else {
408            let s = self[0].sqrt_coefficient()?;
409            if self.data.iter().filter(|x| !x.is_zero()).count()
410                <= deg.next_power_of_two().trailing_zeros() as usize * 4
411            {
412                let t = self[0].clone();
413                let mut f = self / t;
414                f = f.pow_sparse1(T::from(1) / T::from(2), deg);
415                f *= s;
416                return Some(f);
417            }
418
419            let mut f = Self::from(s);
420            let inv2 = T::one() / (T::one() + T::one());
421            let mut i = 1;
422            while i < deg {
423                f = (&f + &(self.prefix_ref(i * 2) * f.inv(i * 2))).prefix(i * 2) * &inv2;
424                i *= 2;
425            }
426            f.truncate(deg);
427            return Some(f);
428        }
429        Some(Self::zeros(deg))
430    }
431}
432
433impl<T, C> FormalPowerSeries<T, C>
434where
435    T: FormalPowerSeriesCoefficient,
436    C: ConvolveSteps<T = Vec<T>>,
437{
438    pub fn count_subset_sum<F>(&self, deg: usize, mut inverse: F) -> Self
439    where
440        F: FnMut(usize) -> T,
441    {
442        let n = self.length();
443        let mut f = Self::zeros(n);
444        for i in 1..n {
445            if !self[i].is_zero() {
446                for (j, d) in (0..n).step_by(i).enumerate().skip(1) {
447                    if j & 1 != 0 {
448                        f[d] += self[i].clone() * &inverse(j);
449                    } else {
450                        f[d] -= self[i].clone() * &inverse(j);
451                    }
452                }
453            }
454        }
455        f.exp(deg)
456    }
457    pub fn count_multiset_sum<F>(&self, deg: usize, mut inverse: F) -> Self
458    where
459        F: FnMut(usize) -> T,
460    {
461        let n = self.length();
462        let mut f = Self::zeros(n);
463        for i in 1..n {
464            if !self[i].is_zero() {
465                for (j, d) in (0..n).step_by(i).enumerate().skip(1) {
466                    f[d] += self[i].clone() * &inverse(j);
467                }
468            }
469        }
470        f.exp(deg)
471    }
472    /// [x^n] P(x) / Q(x)
473    pub fn bostan_mori(mut self, mut rhs: Self, mut n: usize) -> T
474    where
475        C: NttReuse<T = Vec<T>>,
476    {
477        let mut res = T::zero();
478        rhs.trim_tail_zeros();
479        if self.length() >= rhs.length() {
480            let r = &self / &rhs;
481            if n < r.length() {
482                res = r[n].clone();
483            }
484            self -= r * &rhs;
485            self.trim_tail_zeros();
486        }
487        let k = rhs.length().next_power_of_two();
488        let mut p = C::transform(self.data, k * 2);
489        let mut q = C::transform(rhs.data, k * 2);
490        while n > 0 {
491            let t = C::even_mul_normal_neg(&q, &q);
492            p = if n.is_multiple_of(2) {
493                C::even_mul_normal_neg(&p, &q)
494            } else {
495                C::odd_mul_normal_neg(&p, &q)
496            };
497            q = t;
498            n /= 2;
499            if n != 0 {
500                if C::MULTIPLE {
501                    p = C::transform(C::inverse_transform(p, k), k * 2);
502                    q = C::transform(C::inverse_transform(q, k), k * 2);
503                } else {
504                    p = C::ntt_doubling(p);
505                    q = C::ntt_doubling(q);
506                }
507            }
508        }
509        let p = C::inverse_transform(p, k);
510        let q = C::inverse_transform(q, k);
511        res + p[0].clone() / q[0].clone()
512    }
513    /// return F(x) where [x^n] P(x) / Q(x) = [x^d-1] P(x) F(x)
514    pub fn bostan_mori_msb(self, n: usize) -> Self {
515        let d = self.length() - 1;
516        if n == 0 {
517            return (Self::one() << (d - 1)) / self[0].clone();
518        }
519        let q = self;
520        let mq = q.clone().parity_inversion();
521        let w = (q * &mq).even().bostan_mori_msb(n / 2);
522        let mut s = Self::zeros(w.length() * 2 - (n % 2));
523        for (i, x) in w.iter().enumerate() {
524            s[i * 2 + (1 - n % 2)] = x.clone();
525        }
526        let len = 2 * d + 1;
527        let ts = C::transform(s.prefix(len).data, len);
528        mq.reversed().middle_product(&ts, len).prefix(d + 1)
529    }

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

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

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

545    pub fn multipoint_evaluation(self, points: &[T]) -> Vec<T> {
546        let n = points.len();
547        if n <= 32 {
548            return points.iter().map(|p| self.eval(p.clone())).collect();
549        }
550        let mut subproduct_tree = Vec::with_capacity(n * 2);
551        subproduct_tree.resize_with(n, Zero::zero);
552        for x in points {
553            subproduct_tree.push(Self::from_vec(vec![-x.clone(), T::one()]));
554        }
555        for i in (1..n).rev() {
556            subproduct_tree[i] = &subproduct_tree[i * 2] * &subproduct_tree[i * 2 + 1];
557        }
558        let mut uptree_t = Vec::with_capacity(n * 2);
559        uptree_t.resize_with(1, Zero::zero);
560        subproduct_tree.reverse();
561        subproduct_tree.pop();
562        let m = self.length();
563        let v = subproduct_tree.pop().unwrap().reversed().resized(m);
564        let s = C::transform(self.data, m * 2);
565        uptree_t.push(v.inv(m).middle_product(&s, m * 2).resized(n).reversed());
566        for i in 1..n {
567            let subl = subproduct_tree.pop().unwrap();
568            let subr = subproduct_tree.pop().unwrap();
569            let (dl, dr) = (subl.length(), subr.length());
570            let len = dl.max(dr) + uptree_t[i].length();
571            let s = C::transform(uptree_t[i].data.to_vec(), len);
572            uptree_t.push(subr.middle_product(&s, len).prefix(dl));
573            uptree_t.push(subl.middle_product(&s, len).prefix(dr));
574        }
575        uptree_t[n..]
576            .iter()
577            .map(|u| u.data.first().cloned().unwrap_or_else(Zero::zero))
578            .collect()
579    }

Source

pub fn reversed(self) -> Self

Examples found in repository ?

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

514    pub fn bostan_mori_msb(self, n: usize) -> Self {
515        let d = self.length() - 1;
516        if n == 0 {
517            return (Self::one() << (d - 1)) / self[0].clone();
518        }
519        let q = self;
520        let mq = q.clone().parity_inversion();
521        let w = (q * &mq).even().bostan_mori_msb(n / 2);
522        let mut s = Self::zeros(w.length() * 2 - (n % 2));
523        for (i, x) in w.iter().enumerate() {
524            s[i * 2 + (1 - n % 2)] = x.clone();
525        }
526        let len = 2 * d + 1;
527        let ts = C::transform(s.prefix(len).data, len);
528        mq.reversed().middle_product(&ts, len).prefix(d + 1)
529    }
530    /// x^n mod self
531    pub fn pow_mod(self, n: usize) -> Self {
532        let d = self.length() - 1;
533        let q = self.reversed();
534        let u = q.clone().bostan_mori_msb(n);
535        let mut f = (u * q).prefix(d).reversed();
536        f.trim_tail_zeros();
537        f
538    }
539    fn middle_product(self, other: &C::F, deg: usize) -> Self {
540        let n = self.length();
541        let mut s = C::transform(self.reversed().data, deg);
542        C::multiply(&mut s, other);
543        Self::from_vec((C::inverse_transform(s, deg))[n - 1..].to_vec())
544    }
545    pub fn multipoint_evaluation(self, points: &[T]) -> Vec<T> {
546        let n = points.len();
547        if n <= 32 {
548            return points.iter().map(|p| self.eval(p.clone())).collect();
549        }
550        let mut subproduct_tree = Vec::with_capacity(n * 2);
551        subproduct_tree.resize_with(n, Zero::zero);
552        for x in points {
553            subproduct_tree.push(Self::from_vec(vec![-x.clone(), T::one()]));
554        }
555        for i in (1..n).rev() {
556            subproduct_tree[i] = &subproduct_tree[i * 2] * &subproduct_tree[i * 2 + 1];
557        }
558        let mut uptree_t = Vec::with_capacity(n * 2);
559        uptree_t.resize_with(1, Zero::zero);
560        subproduct_tree.reverse();
561        subproduct_tree.pop();
562        let m = self.length();
563        let v = subproduct_tree.pop().unwrap().reversed().resized(m);
564        let s = C::transform(self.data, m * 2);
565        uptree_t.push(v.inv(m).middle_product(&s, m * 2).resized(n).reversed());
566        for i in 1..n {
567            let subl = subproduct_tree.pop().unwrap();
568            let subr = subproduct_tree.pop().unwrap();
569            let (dl, dr) = (subl.length(), subr.length());
570            let len = dl.max(dr) + uptree_t[i].length();
571            let s = C::transform(uptree_t[i].data.to_vec(), len);
572            uptree_t.push(subr.middle_product(&s, len).prefix(dl));
573            uptree_t.push(subl.middle_product(&s, len).prefix(dr));
574        }
575        uptree_t[n..]
576            .iter()
577            .map(|u| u.data.first().cloned().unwrap_or_else(Zero::zero))
578            .collect()
579    }

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

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

More examples

Hide additional examples

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

473    pub fn bostan_mori(mut self, mut rhs: Self, mut n: usize) -> T
474    where
475        C: NttReuse<T = Vec<T>>,
476    {
477        let mut res = T::zero();
478        rhs.trim_tail_zeros();
479        if self.length() >= rhs.length() {
480            let r = &self / &rhs;
481            if n < r.length() {
482                res = r[n].clone();
483            }
484            self -= r * &rhs;
485            self.trim_tail_zeros();
486        }
487        let k = rhs.length().next_power_of_two();
488        let mut p = C::transform(self.data, k * 2);
489        let mut q = C::transform(rhs.data, k * 2);
490        while n > 0 {
491            let t = C::even_mul_normal_neg(&q, &q);
492            p = if n.is_multiple_of(2) {
493                C::even_mul_normal_neg(&p, &q)
494            } else {
495                C::odd_mul_normal_neg(&p, &q)
496            };
497            q = t;
498            n /= 2;
499            if n != 0 {
500                if C::MULTIPLE {
501                    p = C::transform(C::inverse_transform(p, k), k * 2);
502                    q = C::transform(C::inverse_transform(q, k), k * 2);
503                } else {
504                    p = C::ntt_doubling(p);
505                    q = C::ntt_doubling(q);
506                }
507            }
508        }
509        let p = C::inverse_transform(p, k);
510        let q = C::inverse_transform(q, k);
511        res + p[0].clone() / q[0].clone()
512    }
513    /// return F(x) where [x^n] P(x) / Q(x) = [x^d-1] P(x) F(x)
514    pub fn bostan_mori_msb(self, n: usize) -> Self {
515        let d = self.length() - 1;
516        if n == 0 {
517            return (Self::one() << (d - 1)) / self[0].clone();
518        }
519        let q = self;
520        let mq = q.clone().parity_inversion();
521        let w = (q * &mq).even().bostan_mori_msb(n / 2);
522        let mut s = Self::zeros(w.length() * 2 - (n % 2));
523        for (i, x) in w.iter().enumerate() {
524            s[i * 2 + (1 - n % 2)] = x.clone();
525        }
526        let len = 2 * d + 1;
527        let ts = C::transform(s.prefix(len).data, len);
528        mq.reversed().middle_product(&ts, len).prefix(d + 1)
529    }
530    /// x^n mod self
531    pub fn pow_mod(self, n: usize) -> Self {
532        let d = self.length() - 1;
533        let q = self.reversed();
534        let u = q.clone().bostan_mori_msb(n);
535        let mut f = (u * q).prefix(d).reversed();
536        f.trim_tail_zeros();
537        f
538    }

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

248    pub fn inv(&self, deg: usize) -> Self {
249        debug_assert!(!self[0].is_zero());
250        if self.data.iter().filter(|x| !x.is_zero()).count()
251            <= deg.next_power_of_two().trailing_zeros() as usize * 6
252        {
253            let pos: Vec<_> = self
254                .data
255                .iter()
256                .enumerate()
257                .skip(1)
258                .filter_map(|(i, x)| if x.is_zero() { None } else { Some(i) })
259                .collect();
260            let mut f = Self::zeros(deg);
261            f[0] = T::one() / self[0].clone();
262            for i in 1..deg {
263                let mut tot = T::zero();
264                for &j in &pos {
265                    if j > i {
266                        break;
267                    }
268                    tot += self[j].clone() * &f[i - j];
269                }
270                f[i] = -tot * &f[0];
271            }
272            return f;
273        }
274        let mut f = Self::from(T::one() / self[0].clone());
275        let mut i = 1;
276        while i < deg {
277            let g = self.prefix_ref((i * 2).min(deg));
278            let h = f.clone();
279            let mut g = C::transform(g.data, 2 * i);
280            let h = C::transform(h.data, 2 * i);
281            C::multiply(&mut g, &h);
282            let mut g = Self::from_vec(C::inverse_transform(g, 2 * i));
283            g >>= i;
284            let mut g = C::transform(g.data, 2 * i);
285            C::multiply(&mut g, &h);
286            let g = Self::from_vec(C::inverse_transform(g, 2 * i));
287            f.data.extend((-g).into_iter().take(i));
288            i *= 2;
289        }
290        f.truncate(deg);
291        f
292    }
293    pub fn exp(&self, deg: usize) -> Self {
294        debug_assert!(self[0].is_zero());
295        if self.data.iter().filter(|x| !x.is_zero()).count()
296            <= deg.next_power_of_two().trailing_zeros() as usize * 16
297        {
298            let diff = self.clone().diff();
299            let pos: Vec<_> = diff
300                .data
301                .iter()
302                .enumerate()
303                .filter_map(|(i, x)| if x.is_zero() { None } else { Some(i) })
304                .collect();
305            let mf = T::memorized_factorial(deg);
306            let mut f = Self::zeros(deg);
307            f[0] = T::one();
308            for i in 1..deg {
309                let mut tot = T::zero();
310                for &j in &pos {
311                    if j > i - 1 {
312                        break;
313                    }
314                    tot += f[i - 1 - j].clone() * &diff[j];
315                }
316                f[i] = tot * T::memorized_inv(&mf, i);
317            }
318            return f;
319        }
320        let mut f = Self::one();
321        let mut i = 1;
322        while i < deg {
323            let mut g = -f.log(i * 2);
324            g[0] += T::one();
325            for (g, x) in g.iter_mut().zip(self.iter().take(i * 2)) {
326                *g += x.clone();
327            }
328            f = (f * g).prefix(i * 2);
329            i *= 2;
330        }
331        f.prefix(deg)
332    }
333    pub fn log(&self, deg: usize) -> Self {
334        (self.inv(deg) * self.clone().diff()).integral().prefix(deg)
335    }
336    pub fn pow(&self, rhs: usize, deg: usize) -> Self {
337        if rhs == 0 {
338            return Self::from_vec(
339                once(T::one())
340                    .chain(repeat_with(T::zero))
341                    .take(deg)
342                    .collect(),
343            );
344        }
345        if let Some(k) = self.iter().position(|x| !x.is_zero()) {
346            if k >= deg.div_ceil(rhs) {
347                Self::zeros(deg)
348            } else {
349                let deg = deg - k * rhs;
350                let x0 = self[k].clone();
351                let mut f = (self >> k) / &x0;
352                if f.data.iter().filter(|x| !x.is_zero()).count()
353                    <= deg.next_power_of_two().trailing_zeros() as usize * 12
354                {
355                    f = f.pow_sparse1(T::from(rhs), deg);
356                } else {
357                    f = (f.log(deg) * &T::from(rhs)).exp(deg);
358                }
359                f *= x0.pow(rhs);
360                f <<= k * rhs;
361                f
362            }
363        } else {
364            Self::zeros(deg)
365        }
366    }
367    fn pow_sparse1(&self, rhs: T, deg: usize) -> Self {
368        debug_assert!(!self[0].is_zero());
369        let pos: Vec<_> = self
370            .data
371            .iter()
372            .enumerate()
373            .skip(1)
374            .filter_map(|(i, x)| if x.is_zero() { None } else { Some(i) })
375            .collect();
376        let mf = T::memorized_factorial(deg);
377        let mut f = Self::zeros(deg);
378        f[0] = T::one();
379        for i in 1..deg {
380            let mut tot = T::zero();
381            for &j in &pos {
382                if j > i {
383                    break;
384                }
385                tot += (T::from(j) * &rhs - T::from(i - j)) * &self[j] * &f[i - j];
386            }
387            f[i] = tot * T::memorized_inv(&mf, i);
388        }
389        f
390    }
391}
392
393impl<T, C> FormalPowerSeries<T, C>
394where
395    T: FormalPowerSeriesCoefficientSqrt,
396    C: ConvolveSteps<T = Vec<T>>,
397{
398    pub fn sqrt(&self, deg: usize) -> Option<Self> {
399        if self[0].is_zero() {
400            if let Some(k) = self.iter().position(|x| !x.is_zero()) {
401                if k % 2 != 0 {
402                    return None;
403                } else if deg > k / 2 {
404                    return Some((self >> k).sqrt(deg - k / 2)? << (k / 2));
405                }
406            }
407        } else {
408            let s = self[0].sqrt_coefficient()?;
409            if self.data.iter().filter(|x| !x.is_zero()).count()
410                <= deg.next_power_of_two().trailing_zeros() as usize * 4
411            {
412                let t = self[0].clone();
413                let mut f = self / t;
414                f = f.pow_sparse1(T::from(1) / T::from(2), deg);
415                f *= s;
416                return Some(f);
417            }
418
419            let mut f = Self::from(s);
420            let inv2 = T::one() / (T::one() + T::one());
421            let mut i = 1;
422            while i < deg {
423                f = (&f + &(self.prefix_ref(i * 2) * f.inv(i * 2))).prefix(i * 2) * &inv2;
424                i *= 2;
425            }
426            f.truncate(deg);
427            return Some(f);
428        }
429        Some(Self::zeros(deg))
430    }

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

293    pub fn exp(&self, deg: usize) -> Self {
294        debug_assert!(self[0].is_zero());
295        if self.data.iter().filter(|x| !x.is_zero()).count()
296            <= deg.next_power_of_two().trailing_zeros() as usize * 16
297        {
298            let diff = self.clone().diff();
299            let pos: Vec<_> = diff
300                .data
301                .iter()
302                .enumerate()
303                .filter_map(|(i, x)| if x.is_zero() { None } else { Some(i) })
304                .collect();
305            let mf = T::memorized_factorial(deg);
306            let mut f = Self::zeros(deg);
307            f[0] = T::one();
308            for i in 1..deg {
309                let mut tot = T::zero();
310                for &j in &pos {
311                    if j > i - 1 {
312                        break;
313                    }
314                    tot += f[i - 1 - j].clone() * &diff[j];
315                }
316                f[i] = tot * T::memorized_inv(&mf, i);
317            }
318            return f;
319        }
320        let mut f = Self::one();
321        let mut i = 1;
322        while i < deg {
323            let mut g = -f.log(i * 2);
324            g[0] += T::one();
325            for (g, x) in g.iter_mut().zip(self.iter().take(i * 2)) {
326                *g += x.clone();
327            }
328            f = (f * g).prefix(i * 2);
329            i *= 2;
330        }
331        f.prefix(deg)
332    }
333    pub fn log(&self, deg: usize) -> Self {
334        (self.inv(deg) * self.clone().diff()).integral().prefix(deg)
335    }
336    pub fn pow(&self, rhs: usize, deg: usize) -> Self {
337        if rhs == 0 {
338            return Self::from_vec(
339                once(T::one())
340                    .chain(repeat_with(T::zero))
341                    .take(deg)
342                    .collect(),
343            );
344        }
345        if let Some(k) = self.iter().position(|x| !x.is_zero()) {
346            if k >= deg.div_ceil(rhs) {
347                Self::zeros(deg)
348            } else {
349                let deg = deg - k * rhs;
350                let x0 = self[k].clone();
351                let mut f = (self >> k) / &x0;
352                if f.data.iter().filter(|x| !x.is_zero()).count()
353                    <= deg.next_power_of_two().trailing_zeros() as usize * 12
354                {
355                    f = f.pow_sparse1(T::from(rhs), deg);
356                } else {
357                    f = (f.log(deg) * &T::from(rhs)).exp(deg);
358                }
359                f *= x0.pow(rhs);
360                f <<= k * rhs;
361                f
362            }
363        } else {
364            Self::zeros(deg)
365        }
366    }
367    fn pow_sparse1(&self, rhs: T, deg: usize) -> Self {
368        debug_assert!(!self[0].is_zero());
369        let pos: Vec<_> = self
370            .data
371            .iter()
372            .enumerate()
373            .skip(1)
374            .filter_map(|(i, x)| if x.is_zero() { None } else { Some(i) })
375            .collect();
376        let mf = T::memorized_factorial(deg);
377        let mut f = Self::zeros(deg);
378        f[0] = T::one();
379        for i in 1..deg {
380            let mut tot = T::zero();
381            for &j in &pos {
382                if j > i {
383                    break;
384                }
385                tot += (T::from(j) * &rhs - T::from(i - j)) * &self[j] * &f[i - j];
386            }
387            f[i] = tot * T::memorized_inv(&mf, i);
388        }
389        f
390    }
391}
392
393impl<T, C> FormalPowerSeries<T, C>
394where
395    T: FormalPowerSeriesCoefficientSqrt,
396    C: ConvolveSteps<T = Vec<T>>,
397{
398    pub fn sqrt(&self, deg: usize) -> Option<Self> {
399        if self[0].is_zero() {
400            if let Some(k) = self.iter().position(|x| !x.is_zero()) {
401                if k % 2 != 0 {
402                    return None;
403                } else if deg > k / 2 {
404                    return Some((self >> k).sqrt(deg - k / 2)? << (k / 2));
405                }
406            }
407        } else {
408            let s = self[0].sqrt_coefficient()?;
409            if self.data.iter().filter(|x| !x.is_zero()).count()
410                <= deg.next_power_of_two().trailing_zeros() as usize * 4
411            {
412                let t = self[0].clone();
413                let mut f = self / t;
414                f = f.pow_sparse1(T::from(1) / T::from(2), deg);
415                f *= s;
416                return Some(f);
417            }
418
419            let mut f = Self::from(s);
420            let inv2 = T::one() / (T::one() + T::one());
421            let mut i = 1;
422            while i < deg {
423                f = (&f + &(self.prefix_ref(i * 2) * f.inv(i * 2))).prefix(i * 2) * &inv2;
424                i *= 2;
425            }
426            f.truncate(deg);
427            return Some(f);
428        }
429        Some(Self::zeros(deg))
430    }
431}
432
433impl<T, C> FormalPowerSeries<T, C>
434where
435    T: FormalPowerSeriesCoefficient,
436    C: ConvolveSteps<T = Vec<T>>,
437{
438    pub fn count_subset_sum<F>(&self, deg: usize, mut inverse: F) -> Self
439    where
440        F: FnMut(usize) -> T,
441    {
442        let n = self.length();
443        let mut f = Self::zeros(n);
444        for i in 1..n {
445            if !self[i].is_zero() {
446                for (j, d) in (0..n).step_by(i).enumerate().skip(1) {
447                    if j & 1 != 0 {
448                        f[d] += self[i].clone() * &inverse(j);
449                    } else {
450                        f[d] -= self[i].clone() * &inverse(j);
451                    }
452                }
453            }
454        }
455        f.exp(deg)
456    }
457    pub fn count_multiset_sum<F>(&self, deg: usize, mut inverse: F) -> Self
458    where
459        F: FnMut(usize) -> T,
460    {
461        let n = self.length();
462        let mut f = Self::zeros(n);
463        for i in 1..n {
464            if !self[i].is_zero() {
465                for (j, d) in (0..n).step_by(i).enumerate().skip(1) {
466                    f[d] += self[i].clone() * &inverse(j);
467                }
468            }
469        }
470        f.exp(deg)
471    }
472    /// [x^n] P(x) / Q(x)
473    pub fn bostan_mori(mut self, mut rhs: Self, mut n: usize) -> T
474    where
475        C: NttReuse<T = Vec<T>>,
476    {
477        let mut res = T::zero();
478        rhs.trim_tail_zeros();
479        if self.length() >= rhs.length() {
480            let r = &self / &rhs;
481            if n < r.length() {
482                res = r[n].clone();
483            }
484            self -= r * &rhs;
485            self.trim_tail_zeros();
486        }
487        let k = rhs.length().next_power_of_two();
488        let mut p = C::transform(self.data, k * 2);
489        let mut q = C::transform(rhs.data, k * 2);
490        while n > 0 {
491            let t = C::even_mul_normal_neg(&q, &q);
492            p = if n.is_multiple_of(2) {
493                C::even_mul_normal_neg(&p, &q)
494            } else {
495                C::odd_mul_normal_neg(&p, &q)
496            };
497            q = t;
498            n /= 2;
499            if n != 0 {
500                if C::MULTIPLE {
501                    p = C::transform(C::inverse_transform(p, k), k * 2);
502                    q = C::transform(C::inverse_transform(q, k), k * 2);
503                } else {
504                    p = C::ntt_doubling(p);
505                    q = C::ntt_doubling(q);
506                }
507            }
508        }
509        let p = C::inverse_transform(p, k);
510        let q = C::inverse_transform(q, k);
511        res + p[0].clone() / q[0].clone()
512    }
513    /// return F(x) where [x^n] P(x) / Q(x) = [x^d-1] P(x) F(x)
514    pub fn bostan_mori_msb(self, n: usize) -> Self {
515        let d = self.length() - 1;
516        if n == 0 {
517            return (Self::one() << (d - 1)) / self[0].clone();
518        }
519        let q = self;
520        let mq = q.clone().parity_inversion();
521        let w = (q * &mq).even().bostan_mori_msb(n / 2);
522        let mut s = Self::zeros(w.length() * 2 - (n % 2));
523        for (i, x) in w.iter().enumerate() {
524            s[i * 2 + (1 - n % 2)] = x.clone();
525        }
526        let len = 2 * d + 1;
527        let ts = C::transform(s.prefix(len).data, len);
528        mq.reversed().middle_product(&ts, len).prefix(d + 1)
529    }
530    /// x^n mod self
531    pub fn pow_mod(self, n: usize) -> Self {
532        let d = self.length() - 1;
533        let q = self.reversed();
534        let u = q.clone().bostan_mori_msb(n);
535        let mut f = (u * q).prefix(d).reversed();
536        f.trim_tail_zeros();
537        f
538    }
539    fn middle_product(self, other: &C::F, deg: usize) -> Self {
540        let n = self.length();
541        let mut s = C::transform(self.reversed().data, deg);
542        C::multiply(&mut s, other);
543        Self::from_vec((C::inverse_transform(s, deg))[n - 1..].to_vec())
544    }
545    pub fn multipoint_evaluation(self, points: &[T]) -> Vec<T> {
546        let n = points.len();
547        if n <= 32 {
548            return points.iter().map(|p| self.eval(p.clone())).collect();
549        }
550        let mut subproduct_tree = Vec::with_capacity(n * 2);
551        subproduct_tree.resize_with(n, Zero::zero);
552        for x in points {
553            subproduct_tree.push(Self::from_vec(vec![-x.clone(), T::one()]));
554        }
555        for i in (1..n).rev() {
556            subproduct_tree[i] = &subproduct_tree[i * 2] * &subproduct_tree[i * 2 + 1];
557        }
558        let mut uptree_t = Vec::with_capacity(n * 2);
559        uptree_t.resize_with(1, Zero::zero);
560        subproduct_tree.reverse();
561        subproduct_tree.pop();
562        let m = self.length();
563        let v = subproduct_tree.pop().unwrap().reversed().resized(m);
564        let s = C::transform(self.data, m * 2);
565        uptree_t.push(v.inv(m).middle_product(&s, m * 2).resized(n).reversed());
566        for i in 1..n {
567            let subl = subproduct_tree.pop().unwrap();
568            let subr = subproduct_tree.pop().unwrap();
569            let (dl, dr) = (subl.length(), subr.length());
570            let len = dl.max(dr) + uptree_t[i].length();
571            let s = C::transform(uptree_t[i].data.to_vec(), len);
572            uptree_t.push(subr.middle_product(&s, len).prefix(dl));
573            uptree_t.push(subl.middle_product(&s, len).prefix(dr));
574        }
575        uptree_t[n..]
576            .iter()
577            .map(|u| u.data.first().cloned().unwrap_or_else(Zero::zero))
578            .collect()
579    }
580    pub fn product_all<I>(iter: I, deg: usize) -> Self
581    where
582        I: IntoIterator<Item = Self>,
583    {
584        let mut heap: BinaryHeap<_> = iter
585            .into_iter()
586            .map(|f| PartialIgnoredOrd(Reverse(f.length()), f))
587            .collect();
588        while let Some(PartialIgnoredOrd(_, x)) = heap.pop() {
589            if let Some(PartialIgnoredOrd(_, y)) = heap.pop() {
590                let z = (x * y).prefix(deg);
591                heap.push(PartialIgnoredOrd(Reverse(z.length()), z));
592            } else {
593                return x;
594            }
595        }
596        Self::one()
597    }
598    pub fn sum_all_rational<I>(iter: I, deg: usize) -> (Self, Self)
599    where
600        I: IntoIterator<Item = (Self, Self)>,
601    {
602        let mut heap: BinaryHeap<_> = iter
603            .into_iter()
604            .map(|(f, g)| PartialIgnoredOrd(Reverse(f.length().max(g.length())), (f, g)))
605            .collect();
606        while let Some(PartialIgnoredOrd(_, (xa, xb))) = heap.pop() {
607            if let Some(PartialIgnoredOrd(_, (ya, yb))) = heap.pop() {
608                let zb = (&xb * &yb).prefix(deg);
609                let za = (xa * yb + ya * xb).prefix(deg);
610                heap.push(PartialIgnoredOrd(
611                    Reverse(za.length().max(zb.length())),
612                    (za, zb),
613                ));
614            } else {
615                return (xa, xb);
616            }
617        }
618        (Self::zero(), Self::one())
619    }
620    pub fn kth_term_of_linearly_recurrence(self, a: Vec<T>, k: usize) -> T
621    where
622        C: NttReuse<T = Vec<T>>,
623    {
624        if let Some(x) = a.get(k) {
625            return x.clone();
626        }
627        let p = (Self::from_vec(a).prefix(self.length() - 1) * &self).prefix(self.length() - 1);
628        p.bostan_mori(self, k)
629    }
630    pub fn kth_term(a: Vec<T>, k: usize) -> T
631    where
632        C: NttReuse<T = Vec<T>>,
633    {
634        if let Some(x) = a.get(k) {
635            return x.clone();
636        }
637        Self::from_vec(berlekamp_massey(&a)).kth_term_of_linearly_recurrence(a, k)
638    }
639    /// sum_i a_i exp(b_i x)
640    pub fn linear_sum_of_exp<I, F>(iter: I, deg: usize, mut inv_fact: F) -> Self
641    where
642        I: IntoIterator<Item = (T, T)>,
643        F: FnMut(usize) -> T,
644    {
645        let (p, q) = Self::sum_all_rational(
646            iter.into_iter()
647                .map(|(a, b)| (Self::from_vec(vec![a]), Self::from_vec(vec![T::one(), -b]))),
648            deg,
649        );
650        let mut f = (p * q.inv(deg)).prefix(deg);
651        for i in 0..f.length() {
652            f[i] *= inv_fact(i);
653        }
654        f
655    }

Source

pub fn even(self) -> Self

Examples found in repository ?

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

514    pub fn bostan_mori_msb(self, n: usize) -> Self {
515        let d = self.length() - 1;
516        if n == 0 {
517            return (Self::one() << (d - 1)) / self[0].clone();
518        }
519        let q = self;
520        let mq = q.clone().parity_inversion();
521        let w = (q * &mq).even().bostan_mori_msb(n / 2);
522        let mut s = Self::zeros(w.length() * 2 - (n % 2));
523        for (i, x) in w.iter().enumerate() {
524            s[i * 2 + (1 - n % 2)] = x.clone();
525        }
526        let len = 2 * d + 1;
527        let ts = C::transform(s.prefix(len).data, len);
528        mq.reversed().middle_product(&ts, len).prefix(d + 1)
529    }

Source

pub fn odd(self) -> Self

Source

pub fn diff(self) -> Self

Examples found in repository ?

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

293    pub fn exp(&self, deg: usize) -> Self {
294        debug_assert!(self[0].is_zero());
295        if self.data.iter().filter(|x| !x.is_zero()).count()
296            <= deg.next_power_of_two().trailing_zeros() as usize * 16
297        {
298            let diff = self.clone().diff();
299            let pos: Vec<_> = diff
300                .data
301                .iter()
302                .enumerate()
303                .filter_map(|(i, x)| if x.is_zero() { None } else { Some(i) })
304                .collect();
305            let mf = T::memorized_factorial(deg);
306            let mut f = Self::zeros(deg);
307            f[0] = T::one();
308            for i in 1..deg {
309                let mut tot = T::zero();
310                for &j in &pos {
311                    if j > i - 1 {
312                        break;
313                    }
314                    tot += f[i - 1 - j].clone() * &diff[j];
315                }
316                f[i] = tot * T::memorized_inv(&mf, i);
317            }
318            return f;
319        }
320        let mut f = Self::one();
321        let mut i = 1;
322        while i < deg {
323            let mut g = -f.log(i * 2);
324            g[0] += T::one();
325            for (g, x) in g.iter_mut().zip(self.iter().take(i * 2)) {
326                *g += x.clone();
327            }
328            f = (f * g).prefix(i * 2);
329            i *= 2;
330        }
331        f.prefix(deg)
332    }
333    pub fn log(&self, deg: usize) -> Self {
334        (self.inv(deg) * self.clone().diff()).integral().prefix(deg)
335    }
336    pub fn pow(&self, rhs: usize, deg: usize) -> Self {
337        if rhs == 0 {
338            return Self::from_vec(
339                once(T::one())
340                    .chain(repeat_with(T::zero))
341                    .take(deg)
342                    .collect(),
343            );
344        }
345        if let Some(k) = self.iter().position(|x| !x.is_zero()) {
346            if k >= deg.div_ceil(rhs) {
347                Self::zeros(deg)
348            } else {
349                let deg = deg - k * rhs;
350                let x0 = self[k].clone();
351                let mut f = (self >> k) / &x0;
352                if f.data.iter().filter(|x| !x.is_zero()).count()
353                    <= deg.next_power_of_two().trailing_zeros() as usize * 12
354                {
355                    f = f.pow_sparse1(T::from(rhs), deg);
356                } else {
357                    f = (f.log(deg) * &T::from(rhs)).exp(deg);
358                }
359                f *= x0.pow(rhs);
360                f <<= k * rhs;
361                f
362            }
363        } else {
364            Self::zeros(deg)
365        }
366    }
367    fn pow_sparse1(&self, rhs: T, deg: usize) -> Self {
368        debug_assert!(!self[0].is_zero());
369        let pos: Vec<_> = self
370            .data
371            .iter()
372            .enumerate()
373            .skip(1)
374            .filter_map(|(i, x)| if x.is_zero() { None } else { Some(i) })
375            .collect();
376        let mf = T::memorized_factorial(deg);
377        let mut f = Self::zeros(deg);
378        f[0] = T::one();
379        for i in 1..deg {
380            let mut tot = T::zero();
381            for &j in &pos {
382                if j > i {
383                    break;
384                }
385                tot += (T::from(j) * &rhs - T::from(i - j)) * &self[j] * &f[i - j];
386            }
387            f[i] = tot * T::memorized_inv(&mf, i);
388        }
389        f
390    }
391}
392
393impl<T, C> FormalPowerSeries<T, C>
394where
395    T: FormalPowerSeriesCoefficientSqrt,
396    C: ConvolveSteps<T = Vec<T>>,
397{
398    pub fn sqrt(&self, deg: usize) -> Option<Self> {
399        if self[0].is_zero() {
400            if let Some(k) = self.iter().position(|x| !x.is_zero()) {
401                if k % 2 != 0 {
402                    return None;
403                } else if deg > k / 2 {
404                    return Some((self >> k).sqrt(deg - k / 2)? << (k / 2));
405                }
406            }
407        } else {
408            let s = self[0].sqrt_coefficient()?;
409            if self.data.iter().filter(|x| !x.is_zero()).count()
410                <= deg.next_power_of_two().trailing_zeros() as usize * 4
411            {
412                let t = self[0].clone();
413                let mut f = self / t;
414                f = f.pow_sparse1(T::from(1) / T::from(2), deg);
415                f *= s;
416                return Some(f);
417            }
418
419            let mut f = Self::from(s);
420            let inv2 = T::one() / (T::one() + T::one());
421            let mut i = 1;
422            while i < deg {
423                f = (&f + &(self.prefix_ref(i * 2) * f.inv(i * 2))).prefix(i * 2) * &inv2;
424                i *= 2;
425            }
426            f.truncate(deg);
427            return Some(f);
428        }
429        Some(Self::zeros(deg))
430    }
431}
432
433impl<T, C> FormalPowerSeries<T, C>
434where
435    T: FormalPowerSeriesCoefficient,
436    C: ConvolveSteps<T = Vec<T>>,
437{
438    pub fn count_subset_sum<F>(&self, deg: usize, mut inverse: F) -> Self
439    where
440        F: FnMut(usize) -> T,
441    {
442        let n = self.length();
443        let mut f = Self::zeros(n);
444        for i in 1..n {
445            if !self[i].is_zero() {
446                for (j, d) in (0..n).step_by(i).enumerate().skip(1) {
447                    if j & 1 != 0 {
448                        f[d] += self[i].clone() * &inverse(j);
449                    } else {
450                        f[d] -= self[i].clone() * &inverse(j);
451                    }
452                }
453            }
454        }
455        f.exp(deg)
456    }
457    pub fn count_multiset_sum<F>(&self, deg: usize, mut inverse: F) -> Self
458    where
459        F: FnMut(usize) -> T,
460    {
461        let n = self.length();
462        let mut f = Self::zeros(n);
463        for i in 1..n {
464            if !self[i].is_zero() {
465                for (j, d) in (0..n).step_by(i).enumerate().skip(1) {
466                    f[d] += self[i].clone() * &inverse(j);
467                }
468            }
469        }
470        f.exp(deg)
471    }
472    /// [x^n] P(x) / Q(x)
473    pub fn bostan_mori(mut self, mut rhs: Self, mut n: usize) -> T
474    where
475        C: NttReuse<T = Vec<T>>,
476    {
477        let mut res = T::zero();
478        rhs.trim_tail_zeros();
479        if self.length() >= rhs.length() {
480            let r = &self / &rhs;
481            if n < r.length() {
482                res = r[n].clone();
483            }
484            self -= r * &rhs;
485            self.trim_tail_zeros();
486        }
487        let k = rhs.length().next_power_of_two();
488        let mut p = C::transform(self.data, k * 2);
489        let mut q = C::transform(rhs.data, k * 2);
490        while n > 0 {
491            let t = C::even_mul_normal_neg(&q, &q);
492            p = if n.is_multiple_of(2) {
493                C::even_mul_normal_neg(&p, &q)
494            } else {
495                C::odd_mul_normal_neg(&p, &q)
496            };
497            q = t;
498            n /= 2;
499            if n != 0 {
500                if C::MULTIPLE {
501                    p = C::transform(C::inverse_transform(p, k), k * 2);
502                    q = C::transform(C::inverse_transform(q, k), k * 2);
503                } else {
504                    p = C::ntt_doubling(p);
505                    q = C::ntt_doubling(q);
506                }
507            }
508        }
509        let p = C::inverse_transform(p, k);
510        let q = C::inverse_transform(q, k);
511        res + p[0].clone() / q[0].clone()
512    }
513    /// return F(x) where [x^n] P(x) / Q(x) = [x^d-1] P(x) F(x)
514    pub fn bostan_mori_msb(self, n: usize) -> Self {
515        let d = self.length() - 1;
516        if n == 0 {
517            return (Self::one() << (d - 1)) / self[0].clone();
518        }
519        let q = self;
520        let mq = q.clone().parity_inversion();
521        let w = (q * &mq).even().bostan_mori_msb(n / 2);
522        let mut s = Self::zeros(w.length() * 2 - (n % 2));
523        for (i, x) in w.iter().enumerate() {
524            s[i * 2 + (1 - n % 2)] = x.clone();
525        }
526        let len = 2 * d + 1;
527        let ts = C::transform(s.prefix(len).data, len);
528        mq.reversed().middle_product(&ts, len).prefix(d + 1)
529    }
530    /// x^n mod self
531    pub fn pow_mod(self, n: usize) -> Self {
532        let d = self.length() - 1;
533        let q = self.reversed();
534        let u = q.clone().bostan_mori_msb(n);
535        let mut f = (u * q).prefix(d).reversed();
536        f.trim_tail_zeros();
537        f
538    }
539    fn middle_product(self, other: &C::F, deg: usize) -> Self {
540        let n = self.length();
541        let mut s = C::transform(self.reversed().data, deg);
542        C::multiply(&mut s, other);
543        Self::from_vec((C::inverse_transform(s, deg))[n - 1..].to_vec())
544    }
545    pub fn multipoint_evaluation(self, points: &[T]) -> Vec<T> {
546        let n = points.len();
547        if n <= 32 {
548            return points.iter().map(|p| self.eval(p.clone())).collect();
549        }
550        let mut subproduct_tree = Vec::with_capacity(n * 2);
551        subproduct_tree.resize_with(n, Zero::zero);
552        for x in points {
553            subproduct_tree.push(Self::from_vec(vec![-x.clone(), T::one()]));
554        }
555        for i in (1..n).rev() {
556            subproduct_tree[i] = &subproduct_tree[i * 2] * &subproduct_tree[i * 2 + 1];
557        }
558        let mut uptree_t = Vec::with_capacity(n * 2);
559        uptree_t.resize_with(1, Zero::zero);
560        subproduct_tree.reverse();
561        subproduct_tree.pop();
562        let m = self.length();
563        let v = subproduct_tree.pop().unwrap().reversed().resized(m);
564        let s = C::transform(self.data, m * 2);
565        uptree_t.push(v.inv(m).middle_product(&s, m * 2).resized(n).reversed());
566        for i in 1..n {
567            let subl = subproduct_tree.pop().unwrap();
568            let subr = subproduct_tree.pop().unwrap();
569            let (dl, dr) = (subl.length(), subr.length());
570            let len = dl.max(dr) + uptree_t[i].length();
571            let s = C::transform(uptree_t[i].data.to_vec(), len);
572            uptree_t.push(subr.middle_product(&s, len).prefix(dl));
573            uptree_t.push(subl.middle_product(&s, len).prefix(dr));
574        }
575        uptree_t[n..]
576            .iter()
577            .map(|u| u.data.first().cloned().unwrap_or_else(Zero::zero))
578            .collect()
579    }
580    pub fn product_all<I>(iter: I, deg: usize) -> Self
581    where
582        I: IntoIterator<Item = Self>,
583    {
584        let mut heap: BinaryHeap<_> = iter
585            .into_iter()
586            .map(|f| PartialIgnoredOrd(Reverse(f.length()), f))
587            .collect();
588        while let Some(PartialIgnoredOrd(_, x)) = heap.pop() {
589            if let Some(PartialIgnoredOrd(_, y)) = heap.pop() {
590                let z = (x * y).prefix(deg);
591                heap.push(PartialIgnoredOrd(Reverse(z.length()), z));
592            } else {
593                return x;
594            }
595        }
596        Self::one()
597    }
598    pub fn sum_all_rational<I>(iter: I, deg: usize) -> (Self, Self)
599    where
600        I: IntoIterator<Item = (Self, Self)>,
601    {
602        let mut heap: BinaryHeap<_> = iter
603            .into_iter()
604            .map(|(f, g)| PartialIgnoredOrd(Reverse(f.length().max(g.length())), (f, g)))
605            .collect();
606        while let Some(PartialIgnoredOrd(_, (xa, xb))) = heap.pop() {
607            if let Some(PartialIgnoredOrd(_, (ya, yb))) = heap.pop() {
608                let zb = (&xb * &yb).prefix(deg);
609                let za = (xa * yb + ya * xb).prefix(deg);
610                heap.push(PartialIgnoredOrd(
611                    Reverse(za.length().max(zb.length())),
612                    (za, zb),
613                ));
614            } else {
615                return (xa, xb);
616            }
617        }
618        (Self::zero(), Self::one())
619    }
620    pub fn kth_term_of_linearly_recurrence(self, a: Vec<T>, k: usize) -> T
621    where
622        C: NttReuse<T = Vec<T>>,
623    {
624        if let Some(x) = a.get(k) {
625            return x.clone();
626        }
627        let p = (Self::from_vec(a).prefix(self.length() - 1) * &self).prefix(self.length() - 1);
628        p.bostan_mori(self, k)
629    }
630    pub fn kth_term(a: Vec<T>, k: usize) -> T
631    where
632        C: NttReuse<T = Vec<T>>,
633    {
634        if let Some(x) = a.get(k) {
635            return x.clone();
636        }
637        Self::from_vec(berlekamp_massey(&a)).kth_term_of_linearly_recurrence(a, k)
638    }
639    /// sum_i a_i exp(b_i x)
640    pub fn linear_sum_of_exp<I, F>(iter: I, deg: usize, mut inv_fact: F) -> Self
641    where
642        I: IntoIterator<Item = (T, T)>,
643        F: FnMut(usize) -> T,
644    {
645        let (p, q) = Self::sum_all_rational(
646            iter.into_iter()
647                .map(|(a, b)| (Self::from_vec(vec![a]), Self::from_vec(vec![T::one(), -b]))),
648            deg,
649        );
650        let mut f = (p * q.inv(deg)).prefix(deg);
651        for i in 0..f.length() {
652            f[i] *= inv_fact(i);
653        }
654        f
655    }
656    /// sum_i (a_i x)^j
657    pub fn sum_of_powers<I>(iter: I, deg: usize) -> Self
658    where
659        I: IntoIterator<Item = T>,
660    {
661        let mut n = T::zero();
662        let prod = Self::product_all(
663            iter.into_iter().map(|a| {
664                n += T::one();
665                Self::from_vec(vec![T::one(), -a])
666            }),
667            deg,
668        );
669        (-prod.log(deg).diff() << 1) + Self::from_vec(vec![n])
670    }

Source

pub fn integral(self) -> Self

Examples found in repository ?

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

333    pub fn log(&self, deg: usize) -> Self {
334        (self.inv(deg) * self.clone().diff()).integral().prefix(deg)
335    }

Source

pub fn parity_inversion(self) -> Self

Examples found in repository ?

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

514    pub fn bostan_mori_msb(self, n: usize) -> Self {
515        let d = self.length() - 1;
516        if n == 0 {
517            return (Self::one() << (d - 1)) / self[0].clone();
518        }
519        let q = self;
520        let mq = q.clone().parity_inversion();
521        let w = (q * &mq).even().bostan_mori_msb(n / 2);
522        let mut s = Self::zeros(w.length() * 2 - (n % 2));
523        for (i, x) in w.iter().enumerate() {
524            s[i * 2 + (1 - n % 2)] = x.clone();
525        }
526        let len = 2 * d + 1;
527        let ts = C::transform(s.prefix(len).data, len);
528        mq.reversed().middle_product(&ts, len).prefix(d + 1)
529    }

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

545    pub fn multipoint_evaluation(self, points: &[T]) -> Vec<T> {
546        let n = points.len();
547        if n <= 32 {
548            return points.iter().map(|p| self.eval(p.clone())).collect();
549        }
550        let mut subproduct_tree = Vec::with_capacity(n * 2);
551        subproduct_tree.resize_with(n, Zero::zero);
552        for x in points {
553            subproduct_tree.push(Self::from_vec(vec![-x.clone(), T::one()]));
554        }
555        for i in (1..n).rev() {
556            subproduct_tree[i] = &subproduct_tree[i * 2] * &subproduct_tree[i * 2 + 1];
557        }
558        let mut uptree_t = Vec::with_capacity(n * 2);
559        uptree_t.resize_with(1, Zero::zero);
560        subproduct_tree.reverse();
561        subproduct_tree.pop();
562        let m = self.length();
563        let v = subproduct_tree.pop().unwrap().reversed().resized(m);
564        let s = C::transform(self.data, m * 2);
565        uptree_t.push(v.inv(m).middle_product(&s, m * 2).resized(n).reversed());
566        for i in 1..n {
567            let subl = subproduct_tree.pop().unwrap();
568            let subr = subproduct_tree.pop().unwrap();
569            let (dl, dr) = (subl.length(), subr.length());
570            let len = dl.max(dr) + uptree_t[i].length();
571            let s = C::transform(uptree_t[i].data.to_vec(), len);
572            uptree_t.push(subr.middle_product(&s, len).prefix(dl));
573            uptree_t.push(subl.middle_product(&s, len).prefix(dr));
574        }
575        uptree_t[n..]
576            .iter()
577            .map(|u| u.data.first().cloned().unwrap_or_else(Zero::zero))
578            .collect()
579    }

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

333    pub fn log(&self, deg: usize) -> Self {
334        (self.inv(deg) * self.clone().diff()).integral().prefix(deg)
335    }
336    pub fn pow(&self, rhs: usize, deg: usize) -> Self {
337        if rhs == 0 {
338            return Self::from_vec(
339                once(T::one())
340                    .chain(repeat_with(T::zero))
341                    .take(deg)
342                    .collect(),
343            );
344        }
345        if let Some(k) = self.iter().position(|x| !x.is_zero()) {
346            if k >= deg.div_ceil(rhs) {
347                Self::zeros(deg)
348            } else {
349                let deg = deg - k * rhs;
350                let x0 = self[k].clone();
351                let mut f = (self >> k) / &x0;
352                if f.data.iter().filter(|x| !x.is_zero()).count()
353                    <= deg.next_power_of_two().trailing_zeros() as usize * 12
354                {
355                    f = f.pow_sparse1(T::from(rhs), deg);
356                } else {
357                    f = (f.log(deg) * &T::from(rhs)).exp(deg);
358                }
359                f *= x0.pow(rhs);
360                f <<= k * rhs;
361                f
362            }
363        } else {
364            Self::zeros(deg)
365        }
366    }
367    fn pow_sparse1(&self, rhs: T, deg: usize) -> Self {
368        debug_assert!(!self[0].is_zero());
369        let pos: Vec<_> = self
370            .data
371            .iter()
372            .enumerate()
373            .skip(1)
374            .filter_map(|(i, x)| if x.is_zero() { None } else { Some(i) })
375            .collect();
376        let mf = T::memorized_factorial(deg);
377        let mut f = Self::zeros(deg);
378        f[0] = T::one();
379        for i in 1..deg {
380            let mut tot = T::zero();
381            for &j in &pos {
382                if j > i {
383                    break;
384                }
385                tot += (T::from(j) * &rhs - T::from(i - j)) * &self[j] * &f[i - j];
386            }
387            f[i] = tot * T::memorized_inv(&mf, i);
388        }
389        f
390    }
391}
392
393impl<T, C> FormalPowerSeries<T, C>
394where
395    T: FormalPowerSeriesCoefficientSqrt,
396    C: ConvolveSteps<T = Vec<T>>,
397{
398    pub fn sqrt(&self, deg: usize) -> Option<Self> {
399        if self[0].is_zero() {
400            if let Some(k) = self.iter().position(|x| !x.is_zero()) {
401                if k % 2 != 0 {
402                    return None;
403                } else if deg > k / 2 {
404                    return Some((self >> k).sqrt(deg - k / 2)? << (k / 2));
405                }
406            }
407        } else {
408            let s = self[0].sqrt_coefficient()?;
409            if self.data.iter().filter(|x| !x.is_zero()).count()
410                <= deg.next_power_of_two().trailing_zeros() as usize * 4
411            {
412                let t = self[0].clone();
413                let mut f = self / t;
414                f = f.pow_sparse1(T::from(1) / T::from(2), deg);
415                f *= s;
416                return Some(f);
417            }
418
419            let mut f = Self::from(s);
420            let inv2 = T::one() / (T::one() + T::one());
421            let mut i = 1;
422            while i < deg {
423                f = (&f + &(self.prefix_ref(i * 2) * f.inv(i * 2))).prefix(i * 2) * &inv2;
424                i *= 2;
425            }
426            f.truncate(deg);
427            return Some(f);
428        }
429        Some(Self::zeros(deg))
430    }
431}
432
433impl<T, C> FormalPowerSeries<T, C>
434where
435    T: FormalPowerSeriesCoefficient,
436    C: ConvolveSteps<T = Vec<T>>,
437{
438    pub fn count_subset_sum<F>(&self, deg: usize, mut inverse: F) -> Self
439    where
440        F: FnMut(usize) -> T,
441    {
442        let n = self.length();
443        let mut f = Self::zeros(n);
444        for i in 1..n {
445            if !self[i].is_zero() {
446                for (j, d) in (0..n).step_by(i).enumerate().skip(1) {
447                    if j & 1 != 0 {
448                        f[d] += self[i].clone() * &inverse(j);
449                    } else {
450                        f[d] -= self[i].clone() * &inverse(j);
451                    }
452                }
453            }
454        }
455        f.exp(deg)
456    }
457    pub fn count_multiset_sum<F>(&self, deg: usize, mut inverse: F) -> Self
458    where
459        F: FnMut(usize) -> T,
460    {
461        let n = self.length();
462        let mut f = Self::zeros(n);
463        for i in 1..n {
464            if !self[i].is_zero() {
465                for (j, d) in (0..n).step_by(i).enumerate().skip(1) {
466                    f[d] += self[i].clone() * &inverse(j);
467                }
468            }
469        }
470        f.exp(deg)
471    }
472    /// [x^n] P(x) / Q(x)
473    pub fn bostan_mori(mut self, mut rhs: Self, mut n: usize) -> T
474    where
475        C: NttReuse<T = Vec<T>>,
476    {
477        let mut res = T::zero();
478        rhs.trim_tail_zeros();
479        if self.length() >= rhs.length() {
480            let r = &self / &rhs;
481            if n < r.length() {
482                res = r[n].clone();
483            }
484            self -= r * &rhs;
485            self.trim_tail_zeros();
486        }
487        let k = rhs.length().next_power_of_two();
488        let mut p = C::transform(self.data, k * 2);
489        let mut q = C::transform(rhs.data, k * 2);
490        while n > 0 {
491            let t = C::even_mul_normal_neg(&q, &q);
492            p = if n.is_multiple_of(2) {
493                C::even_mul_normal_neg(&p, &q)
494            } else {
495                C::odd_mul_normal_neg(&p, &q)
496            };
497            q = t;
498            n /= 2;
499            if n != 0 {
500                if C::MULTIPLE {
501                    p = C::transform(C::inverse_transform(p, k), k * 2);
502                    q = C::transform(C::inverse_transform(q, k), k * 2);
503                } else {
504                    p = C::ntt_doubling(p);
505                    q = C::ntt_doubling(q);
506                }
507            }
508        }
509        let p = C::inverse_transform(p, k);
510        let q = C::inverse_transform(q, k);
511        res + p[0].clone() / q[0].clone()
512    }
513    /// return F(x) where [x^n] P(x) / Q(x) = [x^d-1] P(x) F(x)
514    pub fn bostan_mori_msb(self, n: usize) -> Self {
515        let d = self.length() - 1;
516        if n == 0 {
517            return (Self::one() << (d - 1)) / self[0].clone();
518        }
519        let q = self;
520        let mq = q.clone().parity_inversion();
521        let w = (q * &mq).even().bostan_mori_msb(n / 2);
522        let mut s = Self::zeros(w.length() * 2 - (n % 2));
523        for (i, x) in w.iter().enumerate() {
524            s[i * 2 + (1 - n % 2)] = x.clone();
525        }
526        let len = 2 * d + 1;
527        let ts = C::transform(s.prefix(len).data, len);
528        mq.reversed().middle_product(&ts, len).prefix(d + 1)
529    }
530    /// x^n mod self
531    pub fn pow_mod(self, n: usize) -> Self {
532        let d = self.length() - 1;
533        let q = self.reversed();
534        let u = q.clone().bostan_mori_msb(n);
535        let mut f = (u * q).prefix(d).reversed();
536        f.trim_tail_zeros();
537        f
538    }
539    fn middle_product(self, other: &C::F, deg: usize) -> Self {
540        let n = self.length();
541        let mut s = C::transform(self.reversed().data, deg);
542        C::multiply(&mut s, other);
543        Self::from_vec((C::inverse_transform(s, deg))[n - 1..].to_vec())
544    }
545    pub fn multipoint_evaluation(self, points: &[T]) -> Vec<T> {
546        let n = points.len();
547        if n <= 32 {
548            return points.iter().map(|p| self.eval(p.clone())).collect();
549        }
550        let mut subproduct_tree = Vec::with_capacity(n * 2);
551        subproduct_tree.resize_with(n, Zero::zero);
552        for x in points {
553            subproduct_tree.push(Self::from_vec(vec![-x.clone(), T::one()]));
554        }
555        for i in (1..n).rev() {
556            subproduct_tree[i] = &subproduct_tree[i * 2] * &subproduct_tree[i * 2 + 1];
557        }
558        let mut uptree_t = Vec::with_capacity(n * 2);
559        uptree_t.resize_with(1, Zero::zero);
560        subproduct_tree.reverse();
561        subproduct_tree.pop();
562        let m = self.length();
563        let v = subproduct_tree.pop().unwrap().reversed().resized(m);
564        let s = C::transform(self.data, m * 2);
565        uptree_t.push(v.inv(m).middle_product(&s, m * 2).resized(n).reversed());
566        for i in 1..n {
567            let subl = subproduct_tree.pop().unwrap();
568            let subr = subproduct_tree.pop().unwrap();
569            let (dl, dr) = (subl.length(), subr.length());
570            let len = dl.max(dr) + uptree_t[i].length();
571            let s = C::transform(uptree_t[i].data.to_vec(), len);
572            uptree_t.push(subr.middle_product(&s, len).prefix(dl));
573            uptree_t.push(subl.middle_product(&s, len).prefix(dr));
574        }
575        uptree_t[n..]
576            .iter()
577            .map(|u| u.data.first().cloned().unwrap_or_else(Zero::zero))
578            .collect()
579    }
580    pub fn product_all<I>(iter: I, deg: usize) -> Self
581    where
582        I: IntoIterator<Item = Self>,
583    {
584        let mut heap: BinaryHeap<_> = iter
585            .into_iter()
586            .map(|f| PartialIgnoredOrd(Reverse(f.length()), f))
587            .collect();
588        while let Some(PartialIgnoredOrd(_, x)) = heap.pop() {
589            if let Some(PartialIgnoredOrd(_, y)) = heap.pop() {
590                let z = (x * y).prefix(deg);
591                heap.push(PartialIgnoredOrd(Reverse(z.length()), z));
592            } else {
593                return x;
594            }
595        }
596        Self::one()
597    }
598    pub fn sum_all_rational<I>(iter: I, deg: usize) -> (Self, Self)
599    where
600        I: IntoIterator<Item = (Self, Self)>,
601    {
602        let mut heap: BinaryHeap<_> = iter
603            .into_iter()
604            .map(|(f, g)| PartialIgnoredOrd(Reverse(f.length().max(g.length())), (f, g)))
605            .collect();
606        while let Some(PartialIgnoredOrd(_, (xa, xb))) = heap.pop() {
607            if let Some(PartialIgnoredOrd(_, (ya, yb))) = heap.pop() {
608                let zb = (&xb * &yb).prefix(deg);
609                let za = (xa * yb + ya * xb).prefix(deg);
610                heap.push(PartialIgnoredOrd(
611                    Reverse(za.length().max(zb.length())),
612                    (za, zb),
613                ));
614            } else {
615                return (xa, xb);
616            }
617        }
618        (Self::zero(), Self::one())
619    }
620    pub fn kth_term_of_linearly_recurrence(self, a: Vec<T>, k: usize) -> T
621    where
622        C: NttReuse<T = Vec<T>>,
623    {
624        if let Some(x) = a.get(k) {
625            return x.clone();
626        }
627        let p = (Self::from_vec(a).prefix(self.length() - 1) * &self).prefix(self.length() - 1);
628        p.bostan_mori(self, k)
629    }
630    pub fn kth_term(a: Vec<T>, k: usize) -> T
631    where
632        C: NttReuse<T = Vec<T>>,
633    {
634        if let Some(x) = a.get(k) {
635            return x.clone();
636        }
637        Self::from_vec(berlekamp_massey(&a)).kth_term_of_linearly_recurrence(a, k)
638    }
639    /// sum_i a_i exp(b_i x)
640    pub fn linear_sum_of_exp<I, F>(iter: I, deg: usize, mut inv_fact: F) -> Self
641    where
642        I: IntoIterator<Item = (T, T)>,
643        F: FnMut(usize) -> T,
644    {
645        let (p, q) = Self::sum_all_rational(
646            iter.into_iter()
647                .map(|(a, b)| (Self::from_vec(vec![a]), Self::from_vec(vec![T::one(), -b]))),
648            deg,
649        );
650        let mut f = (p * q.inv(deg)).prefix(deg);
651        for i in 0..f.length() {
652            f[i] *= inv_fact(i);
653        }
654        f
655    }

More examples

Hide additional examples

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

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

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

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

crates/library_checker/src/polynomial/inv_of_formal_power_series_sparse.rs (line 16)

6pub fn inv_of_formal_power_series_sparse(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, k);
10    let mut a = vec![MInt998244353::zero(); n];
11    for _ in 0..k {
12        scan!(scanner, i, a_i: MInt998244353);
13        a[i] = a_i;
14    }
15    let f = Fps998244353::from_vec(a);
16    let g = f.inv(n);
17    iter_print!(writer, @it g.data);
18}

Source

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

Examples found in repository ?

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

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

More examples

Hide additional examples

crates/library_checker/src/polynomial/exp_of_formal_power_series_sparse.rs (line 16)

6pub fn exp_of_formal_power_series_sparse(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, k);
10    let mut a = vec![MInt998244353::zero(); n];
11    for _ in 0..k {
12        scan!(scanner, i, a_i: MInt998244353);
13        a[i] = a_i;
14    }
15    let f = Fps998244353::from_vec(a);
16    let g = f.exp(n);
17    iter_print!(writer, @it g.data);
18}

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

336    pub fn pow(&self, rhs: usize, deg: usize) -> Self {
337        if rhs == 0 {
338            return Self::from_vec(
339                once(T::one())
340                    .chain(repeat_with(T::zero))
341                    .take(deg)
342                    .collect(),
343            );
344        }
345        if let Some(k) = self.iter().position(|x| !x.is_zero()) {
346            if k >= deg.div_ceil(rhs) {
347                Self::zeros(deg)
348            } else {
349                let deg = deg - k * rhs;
350                let x0 = self[k].clone();
351                let mut f = (self >> k) / &x0;
352                if f.data.iter().filter(|x| !x.is_zero()).count()
353                    <= deg.next_power_of_two().trailing_zeros() as usize * 12
354                {
355                    f = f.pow_sparse1(T::from(rhs), deg);
356                } else {
357                    f = (f.log(deg) * &T::from(rhs)).exp(deg);
358                }
359                f *= x0.pow(rhs);
360                f <<= k * rhs;
361                f
362            }
363        } else {
364            Self::zeros(deg)
365        }
366    }
367    fn pow_sparse1(&self, rhs: T, deg: usize) -> Self {
368        debug_assert!(!self[0].is_zero());
369        let pos: Vec<_> = self
370            .data
371            .iter()
372            .enumerate()
373            .skip(1)
374            .filter_map(|(i, x)| if x.is_zero() { None } else { Some(i) })
375            .collect();
376        let mf = T::memorized_factorial(deg);
377        let mut f = Self::zeros(deg);
378        f[0] = T::one();
379        for i in 1..deg {
380            let mut tot = T::zero();
381            for &j in &pos {
382                if j > i {
383                    break;
384                }
385                tot += (T::from(j) * &rhs - T::from(i - j)) * &self[j] * &f[i - j];
386            }
387            f[i] = tot * T::memorized_inv(&mf, i);
388        }
389        f
390    }
391}
392
393impl<T, C> FormalPowerSeries<T, C>
394where
395    T: FormalPowerSeriesCoefficientSqrt,
396    C: ConvolveSteps<T = Vec<T>>,
397{
398    pub fn sqrt(&self, deg: usize) -> Option<Self> {
399        if self[0].is_zero() {
400            if let Some(k) = self.iter().position(|x| !x.is_zero()) {
401                if k % 2 != 0 {
402                    return None;
403                } else if deg > k / 2 {
404                    return Some((self >> k).sqrt(deg - k / 2)? << (k / 2));
405                }
406            }
407        } else {
408            let s = self[0].sqrt_coefficient()?;
409            if self.data.iter().filter(|x| !x.is_zero()).count()
410                <= deg.next_power_of_two().trailing_zeros() as usize * 4
411            {
412                let t = self[0].clone();
413                let mut f = self / t;
414                f = f.pow_sparse1(T::from(1) / T::from(2), deg);
415                f *= s;
416                return Some(f);
417            }
418
419            let mut f = Self::from(s);
420            let inv2 = T::one() / (T::one() + T::one());
421            let mut i = 1;
422            while i < deg {
423                f = (&f + &(self.prefix_ref(i * 2) * f.inv(i * 2))).prefix(i * 2) * &inv2;
424                i *= 2;
425            }
426            f.truncate(deg);
427            return Some(f);
428        }
429        Some(Self::zeros(deg))
430    }
431}
432
433impl<T, C> FormalPowerSeries<T, C>
434where
435    T: FormalPowerSeriesCoefficient,
436    C: ConvolveSteps<T = Vec<T>>,
437{
438    pub fn count_subset_sum<F>(&self, deg: usize, mut inverse: F) -> Self
439    where
440        F: FnMut(usize) -> T,
441    {
442        let n = self.length();
443        let mut f = Self::zeros(n);
444        for i in 1..n {
445            if !self[i].is_zero() {
446                for (j, d) in (0..n).step_by(i).enumerate().skip(1) {
447                    if j & 1 != 0 {
448                        f[d] += self[i].clone() * &inverse(j);
449                    } else {
450                        f[d] -= self[i].clone() * &inverse(j);
451                    }
452                }
453            }
454        }
455        f.exp(deg)
456    }
457    pub fn count_multiset_sum<F>(&self, deg: usize, mut inverse: F) -> Self
458    where
459        F: FnMut(usize) -> T,
460    {
461        let n = self.length();
462        let mut f = Self::zeros(n);
463        for i in 1..n {
464            if !self[i].is_zero() {
465                for (j, d) in (0..n).step_by(i).enumerate().skip(1) {
466                    f[d] += self[i].clone() * &inverse(j);
467                }
468            }
469        }
470        f.exp(deg)
471    }

Source

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

Examples found in repository ?

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

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

More examples

Hide additional examples

crates/library_checker/src/polynomial/log_of_formal_power_series_sparse.rs (line 16)

6pub fn log_of_formal_power_series_sparse(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, k);
10    let mut a = vec![MInt998244353::zero(); n];
11    for _ in 0..k {
12        scan!(scanner, i, a_i: MInt998244353);
13        a[i] = a_i;
14    }
15    let f = Fps998244353::from_vec(a);
16    let g = f.log(n);
17    iter_print!(writer, @it g.data);
18}

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

293    pub fn exp(&self, deg: usize) -> Self {
294        debug_assert!(self[0].is_zero());
295        if self.data.iter().filter(|x| !x.is_zero()).count()
296            <= deg.next_power_of_two().trailing_zeros() as usize * 16
297        {
298            let diff = self.clone().diff();
299            let pos: Vec<_> = diff
300                .data
301                .iter()
302                .enumerate()
303                .filter_map(|(i, x)| if x.is_zero() { None } else { Some(i) })
304                .collect();
305            let mf = T::memorized_factorial(deg);
306            let mut f = Self::zeros(deg);
307            f[0] = T::one();
308            for i in 1..deg {
309                let mut tot = T::zero();
310                for &j in &pos {
311                    if j > i - 1 {
312                        break;
313                    }
314                    tot += f[i - 1 - j].clone() * &diff[j];
315                }
316                f[i] = tot * T::memorized_inv(&mf, i);
317            }
318            return f;
319        }
320        let mut f = Self::one();
321        let mut i = 1;
322        while i < deg {
323            let mut g = -f.log(i * 2);
324            g[0] += T::one();
325            for (g, x) in g.iter_mut().zip(self.iter().take(i * 2)) {
326                *g += x.clone();
327            }
328            f = (f * g).prefix(i * 2);
329            i *= 2;
330        }
331        f.prefix(deg)
332    }
333    pub fn log(&self, deg: usize) -> Self {
334        (self.inv(deg) * self.clone().diff()).integral().prefix(deg)
335    }
336    pub fn pow(&self, rhs: usize, deg: usize) -> Self {
337        if rhs == 0 {
338            return Self::from_vec(
339                once(T::one())
340                    .chain(repeat_with(T::zero))
341                    .take(deg)
342                    .collect(),
343            );
344        }
345        if let Some(k) = self.iter().position(|x| !x.is_zero()) {
346            if k >= deg.div_ceil(rhs) {
347                Self::zeros(deg)
348            } else {
349                let deg = deg - k * rhs;
350                let x0 = self[k].clone();
351                let mut f = (self >> k) / &x0;
352                if f.data.iter().filter(|x| !x.is_zero()).count()
353                    <= deg.next_power_of_two().trailing_zeros() as usize * 12
354                {
355                    f = f.pow_sparse1(T::from(rhs), deg);
356                } else {
357                    f = (f.log(deg) * &T::from(rhs)).exp(deg);
358                }
359                f *= x0.pow(rhs);
360                f <<= k * rhs;
361                f
362            }
363        } else {
364            Self::zeros(deg)
365        }
366    }
367    fn pow_sparse1(&self, rhs: T, deg: usize) -> Self {
368        debug_assert!(!self[0].is_zero());
369        let pos: Vec<_> = self
370            .data
371            .iter()
372            .enumerate()
373            .skip(1)
374            .filter_map(|(i, x)| if x.is_zero() { None } else { Some(i) })
375            .collect();
376        let mf = T::memorized_factorial(deg);
377        let mut f = Self::zeros(deg);
378        f[0] = T::one();
379        for i in 1..deg {
380            let mut tot = T::zero();
381            for &j in &pos {
382                if j > i {
383                    break;
384                }
385                tot += (T::from(j) * &rhs - T::from(i - j)) * &self[j] * &f[i - j];
386            }
387            f[i] = tot * T::memorized_inv(&mf, i);
388        }
389        f
390    }
391}
392
393impl<T, C> FormalPowerSeries<T, C>
394where
395    T: FormalPowerSeriesCoefficientSqrt,
396    C: ConvolveSteps<T = Vec<T>>,
397{
398    pub fn sqrt(&self, deg: usize) -> Option<Self> {
399        if self[0].is_zero() {
400            if let Some(k) = self.iter().position(|x| !x.is_zero()) {
401                if k % 2 != 0 {
402                    return None;
403                } else if deg > k / 2 {
404                    return Some((self >> k).sqrt(deg - k / 2)? << (k / 2));
405                }
406            }
407        } else {
408            let s = self[0].sqrt_coefficient()?;
409            if self.data.iter().filter(|x| !x.is_zero()).count()
410                <= deg.next_power_of_two().trailing_zeros() as usize * 4
411            {
412                let t = self[0].clone();
413                let mut f = self / t;
414                f = f.pow_sparse1(T::from(1) / T::from(2), deg);
415                f *= s;
416                return Some(f);
417            }
418
419            let mut f = Self::from(s);
420            let inv2 = T::one() / (T::one() + T::one());
421            let mut i = 1;
422            while i < deg {
423                f = (&f + &(self.prefix_ref(i * 2) * f.inv(i * 2))).prefix(i * 2) * &inv2;
424                i *= 2;
425            }
426            f.truncate(deg);
427            return Some(f);
428        }
429        Some(Self::zeros(deg))
430    }
431}
432
433impl<T, C> FormalPowerSeries<T, C>
434where
435    T: FormalPowerSeriesCoefficient,
436    C: ConvolveSteps<T = Vec<T>>,
437{
438    pub fn count_subset_sum<F>(&self, deg: usize, mut inverse: F) -> Self
439    where
440        F: FnMut(usize) -> T,
441    {
442        let n = self.length();
443        let mut f = Self::zeros(n);
444        for i in 1..n {
445            if !self[i].is_zero() {
446                for (j, d) in (0..n).step_by(i).enumerate().skip(1) {
447                    if j & 1 != 0 {
448                        f[d] += self[i].clone() * &inverse(j);
449                    } else {
450                        f[d] -= self[i].clone() * &inverse(j);
451                    }
452                }
453            }
454        }
455        f.exp(deg)
456    }
457    pub fn count_multiset_sum<F>(&self, deg: usize, mut inverse: F) -> Self
458    where
459        F: FnMut(usize) -> T,
460    {
461        let n = self.length();
462        let mut f = Self::zeros(n);
463        for i in 1..n {
464            if !self[i].is_zero() {
465                for (j, d) in (0..n).step_by(i).enumerate().skip(1) {
466                    f[d] += self[i].clone() * &inverse(j);
467                }
468            }
469        }
470        f.exp(deg)
471    }
472    /// [x^n] P(x) / Q(x)
473    pub fn bostan_mori(mut self, mut rhs: Self, mut n: usize) -> T
474    where
475        C: NttReuse<T = Vec<T>>,
476    {
477        let mut res = T::zero();
478        rhs.trim_tail_zeros();
479        if self.length() >= rhs.length() {
480            let r = &self / &rhs;
481            if n < r.length() {
482                res = r[n].clone();
483            }
484            self -= r * &rhs;
485            self.trim_tail_zeros();
486        }
487        let k = rhs.length().next_power_of_two();
488        let mut p = C::transform(self.data, k * 2);
489        let mut q = C::transform(rhs.data, k * 2);
490        while n > 0 {
491            let t = C::even_mul_normal_neg(&q, &q);
492            p = if n.is_multiple_of(2) {
493                C::even_mul_normal_neg(&p, &q)
494            } else {
495                C::odd_mul_normal_neg(&p, &q)
496            };
497            q = t;
498            n /= 2;
499            if n != 0 {
500                if C::MULTIPLE {
501                    p = C::transform(C::inverse_transform(p, k), k * 2);
502                    q = C::transform(C::inverse_transform(q, k), k * 2);
503                } else {
504                    p = C::ntt_doubling(p);
505                    q = C::ntt_doubling(q);
506                }
507            }
508        }
509        let p = C::inverse_transform(p, k);
510        let q = C::inverse_transform(q, k);
511        res + p[0].clone() / q[0].clone()
512    }
513    /// return F(x) where [x^n] P(x) / Q(x) = [x^d-1] P(x) F(x)
514    pub fn bostan_mori_msb(self, n: usize) -> Self {
515        let d = self.length() - 1;
516        if n == 0 {
517            return (Self::one() << (d - 1)) / self[0].clone();
518        }
519        let q = self;
520        let mq = q.clone().parity_inversion();
521        let w = (q * &mq).even().bostan_mori_msb(n / 2);
522        let mut s = Self::zeros(w.length() * 2 - (n % 2));
523        for (i, x) in w.iter().enumerate() {
524            s[i * 2 + (1 - n % 2)] = x.clone();
525        }
526        let len = 2 * d + 1;
527        let ts = C::transform(s.prefix(len).data, len);
528        mq.reversed().middle_product(&ts, len).prefix(d + 1)
529    }
530    /// x^n mod self
531    pub fn pow_mod(self, n: usize) -> Self {
532        let d = self.length() - 1;
533        let q = self.reversed();
534        let u = q.clone().bostan_mori_msb(n);
535        let mut f = (u * q).prefix(d).reversed();
536        f.trim_tail_zeros();
537        f
538    }
539    fn middle_product(self, other: &C::F, deg: usize) -> Self {
540        let n = self.length();
541        let mut s = C::transform(self.reversed().data, deg);
542        C::multiply(&mut s, other);
543        Self::from_vec((C::inverse_transform(s, deg))[n - 1..].to_vec())
544    }
545    pub fn multipoint_evaluation(self, points: &[T]) -> Vec<T> {
546        let n = points.len();
547        if n <= 32 {
548            return points.iter().map(|p| self.eval(p.clone())).collect();
549        }
550        let mut subproduct_tree = Vec::with_capacity(n * 2);
551        subproduct_tree.resize_with(n, Zero::zero);
552        for x in points {
553            subproduct_tree.push(Self::from_vec(vec![-x.clone(), T::one()]));
554        }
555        for i in (1..n).rev() {
556            subproduct_tree[i] = &subproduct_tree[i * 2] * &subproduct_tree[i * 2 + 1];
557        }
558        let mut uptree_t = Vec::with_capacity(n * 2);
559        uptree_t.resize_with(1, Zero::zero);
560        subproduct_tree.reverse();
561        subproduct_tree.pop();
562        let m = self.length();
563        let v = subproduct_tree.pop().unwrap().reversed().resized(m);
564        let s = C::transform(self.data, m * 2);
565        uptree_t.push(v.inv(m).middle_product(&s, m * 2).resized(n).reversed());
566        for i in 1..n {
567            let subl = subproduct_tree.pop().unwrap();
568            let subr = subproduct_tree.pop().unwrap();
569            let (dl, dr) = (subl.length(), subr.length());
570            let len = dl.max(dr) + uptree_t[i].length();
571            let s = C::transform(uptree_t[i].data.to_vec(), len);
572            uptree_t.push(subr.middle_product(&s, len).prefix(dl));
573            uptree_t.push(subl.middle_product(&s, len).prefix(dr));
574        }
575        uptree_t[n..]
576            .iter()
577            .map(|u| u.data.first().cloned().unwrap_or_else(Zero::zero))
578            .collect()
579    }
580    pub fn product_all<I>(iter: I, deg: usize) -> Self
581    where
582        I: IntoIterator<Item = Self>,
583    {
584        let mut heap: BinaryHeap<_> = iter
585            .into_iter()
586            .map(|f| PartialIgnoredOrd(Reverse(f.length()), f))
587            .collect();
588        while let Some(PartialIgnoredOrd(_, x)) = heap.pop() {
589            if let Some(PartialIgnoredOrd(_, y)) = heap.pop() {
590                let z = (x * y).prefix(deg);
591                heap.push(PartialIgnoredOrd(Reverse(z.length()), z));
592            } else {
593                return x;
594            }
595        }
596        Self::one()
597    }
598    pub fn sum_all_rational<I>(iter: I, deg: usize) -> (Self, Self)
599    where
600        I: IntoIterator<Item = (Self, Self)>,
601    {
602        let mut heap: BinaryHeap<_> = iter
603            .into_iter()
604            .map(|(f, g)| PartialIgnoredOrd(Reverse(f.length().max(g.length())), (f, g)))
605            .collect();
606        while let Some(PartialIgnoredOrd(_, (xa, xb))) = heap.pop() {
607            if let Some(PartialIgnoredOrd(_, (ya, yb))) = heap.pop() {
608                let zb = (&xb * &yb).prefix(deg);
609                let za = (xa * yb + ya * xb).prefix(deg);
610                heap.push(PartialIgnoredOrd(
611                    Reverse(za.length().max(zb.length())),
612                    (za, zb),
613                ));
614            } else {
615                return (xa, xb);
616            }
617        }
618        (Self::zero(), Self::one())
619    }
620    pub fn kth_term_of_linearly_recurrence(self, a: Vec<T>, k: usize) -> T
621    where
622        C: NttReuse<T = Vec<T>>,
623    {
624        if let Some(x) = a.get(k) {
625            return x.clone();
626        }
627        let p = (Self::from_vec(a).prefix(self.length() - 1) * &self).prefix(self.length() - 1);
628        p.bostan_mori(self, k)
629    }
630    pub fn kth_term(a: Vec<T>, k: usize) -> T
631    where
632        C: NttReuse<T = Vec<T>>,
633    {
634        if let Some(x) = a.get(k) {
635            return x.clone();
636        }
637        Self::from_vec(berlekamp_massey(&a)).kth_term_of_linearly_recurrence(a, k)
638    }
639    /// sum_i a_i exp(b_i x)
640    pub fn linear_sum_of_exp<I, F>(iter: I, deg: usize, mut inv_fact: F) -> Self
641    where
642        I: IntoIterator<Item = (T, T)>,
643        F: FnMut(usize) -> T,
644    {
645        let (p, q) = Self::sum_all_rational(
646            iter.into_iter()
647                .map(|(a, b)| (Self::from_vec(vec![a]), Self::from_vec(vec![T::one(), -b]))),
648            deg,
649        );
650        let mut f = (p * q.inv(deg)).prefix(deg);
651        for i in 0..f.length() {
652            f[i] *= inv_fact(i);
653        }
654        f
655    }
656    /// sum_i (a_i x)^j
657    pub fn sum_of_powers<I>(iter: I, deg: usize) -> Self
658    where
659        I: IntoIterator<Item = T>,
660    {
661        let mut n = T::zero();
662        let prod = Self::product_all(
663            iter.into_iter().map(|a| {
664                n += T::one();
665                Self::from_vec(vec![T::one(), -a])
666            }),
667            deg,
668        );
669        (-prod.log(deg).diff() << 1) + Self::from_vec(vec![n])
670    }

Source

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

Examples found in repository ?

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

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

More examples

Hide additional examples

crates/library_checker/src/polynomial/pow_of_formal_power_series_sparse.rs (line 16)

6pub fn pow_of_formal_power_series_sparse(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, k, m);
10    let mut a = vec![MInt998244353::zero(); n];
11    for _ in 0..k {
12        scan!(scanner, i, a_i: MInt998244353);
13        a[i] = a_i;
14    }
15    let f = Fps998244353::from_vec(a);
16    let g = f.pow(m, n);
17    iter_print!(writer, @it g.data);
18}

Source

fn pow_sparse1(&self, rhs: T, deg: usize) -> Self

Examples found in repository ?

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

336    pub fn pow(&self, rhs: usize, deg: usize) -> Self {
337        if rhs == 0 {
338            return Self::from_vec(
339                once(T::one())
340                    .chain(repeat_with(T::zero))
341                    .take(deg)
342                    .collect(),
343            );
344        }
345        if let Some(k) = self.iter().position(|x| !x.is_zero()) {
346            if k >= deg.div_ceil(rhs) {
347                Self::zeros(deg)
348            } else {
349                let deg = deg - k * rhs;
350                let x0 = self[k].clone();
351                let mut f = (self >> k) / &x0;
352                if f.data.iter().filter(|x| !x.is_zero()).count()
353                    <= deg.next_power_of_two().trailing_zeros() as usize * 12
354                {
355                    f = f.pow_sparse1(T::from(rhs), deg);
356                } else {
357                    f = (f.log(deg) * &T::from(rhs)).exp(deg);
358                }
359                f *= x0.pow(rhs);
360                f <<= k * rhs;
361                f
362            }
363        } else {
364            Self::zeros(deg)
365        }
366    }
367    fn pow_sparse1(&self, rhs: T, deg: usize) -> Self {
368        debug_assert!(!self[0].is_zero());
369        let pos: Vec<_> = self
370            .data
371            .iter()
372            .enumerate()
373            .skip(1)
374            .filter_map(|(i, x)| if x.is_zero() { None } else { Some(i) })
375            .collect();
376        let mf = T::memorized_factorial(deg);
377        let mut f = Self::zeros(deg);
378        f[0] = T::one();
379        for i in 1..deg {
380            let mut tot = T::zero();
381            for &j in &pos {
382                if j > i {
383                    break;
384                }
385                tot += (T::from(j) * &rhs - T::from(i - j)) * &self[j] * &f[i - j];
386            }
387            f[i] = tot * T::memorized_inv(&mf, i);
388        }
389        f
390    }
391}
392
393impl<T, C> FormalPowerSeries<T, C>
394where
395    T: FormalPowerSeriesCoefficientSqrt,
396    C: ConvolveSteps<T = Vec<T>>,
397{
398    pub fn sqrt(&self, deg: usize) -> Option<Self> {
399        if self[0].is_zero() {
400            if let Some(k) = self.iter().position(|x| !x.is_zero()) {
401                if k % 2 != 0 {
402                    return None;
403                } else if deg > k / 2 {
404                    return Some((self >> k).sqrt(deg - k / 2)? << (k / 2));
405                }
406            }
407        } else {
408            let s = self[0].sqrt_coefficient()?;
409            if self.data.iter().filter(|x| !x.is_zero()).count()
410                <= deg.next_power_of_two().trailing_zeros() as usize * 4
411            {
412                let t = self[0].clone();
413                let mut f = self / t;
414                f = f.pow_sparse1(T::from(1) / T::from(2), deg);
415                f *= s;
416                return Some(f);
417            }
418
419            let mut f = Self::from(s);
420            let inv2 = T::one() / (T::one() + T::one());
421            let mut i = 1;
422            while i < deg {
423                f = (&f + &(self.prefix_ref(i * 2) * f.inv(i * 2))).prefix(i * 2) * &inv2;
424                i *= 2;
425            }
426            f.truncate(deg);
427            return Some(f);
428        }
429        Some(Self::zeros(deg))
430    }

Source §

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

Source

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

Examples found in repository ?

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

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

More examples

Hide additional examples

crates/library_checker/src/polynomial/sqrt_of_formal_power_series_sparse.rs (line 16)

6pub fn sqrt_of_formal_power_series_sparse(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, k);
10    let mut a = vec![MInt998244353::zero(); n];
11    for _ in 0..k {
12        scan!(scanner, i, a_i: MInt998244353);
13        a[i] = a_i;
14    }
15    let f = Fps998244353::from_vec(a);
16    if let Some(g) = f.sqrt(n) {
17        iter_print!(writer, @it g.data);
18    } else {
19        iter_print!(writer, "-1");
20    }
21}

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

398    pub fn sqrt(&self, deg: usize) -> Option<Self> {
399        if self[0].is_zero() {
400            if let Some(k) = self.iter().position(|x| !x.is_zero()) {
401                if k % 2 != 0 {
402                    return None;
403                } else if deg > k / 2 {
404                    return Some((self >> k).sqrt(deg - k / 2)? << (k / 2));
405                }
406            }
407        } else {
408            let s = self[0].sqrt_coefficient()?;
409            if self.data.iter().filter(|x| !x.is_zero()).count()
410                <= deg.next_power_of_two().trailing_zeros() as usize * 4
411            {
412                let t = self[0].clone();
413                let mut f = self / t;
414                f = f.pow_sparse1(T::from(1) / T::from(2), deg);
415                f *= s;
416                return Some(f);
417            }
418
419            let mut f = Self::from(s);
420            let inv2 = T::one() / (T::one() + T::one());
421            let mut i = 1;
422            while i < deg {
423                f = (&f + &(self.prefix_ref(i * 2) * f.inv(i * 2))).prefix(i * 2) * &inv2;
424                i *= 2;
425            }
426            f.truncate(deg);
427            return Some(f);
428        }
429        Some(Self::zeros(deg))
430    }

Source §

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

Source

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

Examples found in repository ?

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

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

Source

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

Source

pub fn bostan_mori(self, rhs: Self, n: usize) -> T
where C: NttReuse<T = Vec<T>>,

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

Examples found in repository ?

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

620    pub fn kth_term_of_linearly_recurrence(self, a: Vec<T>, k: usize) -> T
621    where
622        C: NttReuse<T = Vec<T>>,
623    {
624        if let Some(x) = a.get(k) {
625            return x.clone();
626        }
627        let p = (Self::from_vec(a).prefix(self.length() - 1) * &self).prefix(self.length() - 1);
628        p.bostan_mori(self, k)
629    }

Source

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

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

Examples found in repository ?

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

514    pub fn bostan_mori_msb(self, n: usize) -> Self {
515        let d = self.length() - 1;
516        if n == 0 {
517            return (Self::one() << (d - 1)) / self[0].clone();
518        }
519        let q = self;
520        let mq = q.clone().parity_inversion();
521        let w = (q * &mq).even().bostan_mori_msb(n / 2);
522        let mut s = Self::zeros(w.length() * 2 - (n % 2));
523        for (i, x) in w.iter().enumerate() {
524            s[i * 2 + (1 - n % 2)] = x.clone();
525        }
526        let len = 2 * d + 1;
527        let ts = C::transform(s.prefix(len).data, len);
528        mq.reversed().middle_product(&ts, len).prefix(d + 1)
529    }
530    /// x^n mod self
531    pub fn pow_mod(self, n: usize) -> Self {
532        let d = self.length() - 1;
533        let q = self.reversed();
534        let u = q.clone().bostan_mori_msb(n);
535        let mut f = (u * q).prefix(d).reversed();
536        f.trim_tail_zeros();
537        f
538    }

Source

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

x^n mod self

Examples found in repository ?

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

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

Source

fn middle_product(self, other: &C::F, deg: usize) -> Self

Examples found in repository ?

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

514    pub fn bostan_mori_msb(self, n: usize) -> Self {
515        let d = self.length() - 1;
516        if n == 0 {
517            return (Self::one() << (d - 1)) / self[0].clone();
518        }
519        let q = self;
520        let mq = q.clone().parity_inversion();
521        let w = (q * &mq).even().bostan_mori_msb(n / 2);
522        let mut s = Self::zeros(w.length() * 2 - (n % 2));
523        for (i, x) in w.iter().enumerate() {
524            s[i * 2 + (1 - n % 2)] = x.clone();
525        }
526        let len = 2 * d + 1;
527        let ts = C::transform(s.prefix(len).data, len);
528        mq.reversed().middle_product(&ts, len).prefix(d + 1)
529    }
530    /// x^n mod self
531    pub fn pow_mod(self, n: usize) -> Self {
532        let d = self.length() - 1;
533        let q = self.reversed();
534        let u = q.clone().bostan_mori_msb(n);
535        let mut f = (u * q).prefix(d).reversed();
536        f.trim_tail_zeros();
537        f
538    }
539    fn middle_product(self, other: &C::F, deg: usize) -> Self {
540        let n = self.length();
541        let mut s = C::transform(self.reversed().data, deg);
542        C::multiply(&mut s, other);
543        Self::from_vec((C::inverse_transform(s, deg))[n - 1..].to_vec())
544    }
545    pub fn multipoint_evaluation(self, points: &[T]) -> Vec<T> {
546        let n = points.len();
547        if n <= 32 {
548            return points.iter().map(|p| self.eval(p.clone())).collect();
549        }
550        let mut subproduct_tree = Vec::with_capacity(n * 2);
551        subproduct_tree.resize_with(n, Zero::zero);
552        for x in points {
553            subproduct_tree.push(Self::from_vec(vec![-x.clone(), T::one()]));
554        }
555        for i in (1..n).rev() {
556            subproduct_tree[i] = &subproduct_tree[i * 2] * &subproduct_tree[i * 2 + 1];
557        }
558        let mut uptree_t = Vec::with_capacity(n * 2);
559        uptree_t.resize_with(1, Zero::zero);
560        subproduct_tree.reverse();
561        subproduct_tree.pop();
562        let m = self.length();
563        let v = subproduct_tree.pop().unwrap().reversed().resized(m);
564        let s = C::transform(self.data, m * 2);
565        uptree_t.push(v.inv(m).middle_product(&s, m * 2).resized(n).reversed());
566        for i in 1..n {
567            let subl = subproduct_tree.pop().unwrap();
568            let subr = subproduct_tree.pop().unwrap();
569            let (dl, dr) = (subl.length(), subr.length());
570            let len = dl.max(dr) + uptree_t[i].length();
571            let s = C::transform(uptree_t[i].data.to_vec(), len);
572            uptree_t.push(subr.middle_product(&s, len).prefix(dl));
573            uptree_t.push(subl.middle_product(&s, len).prefix(dr));
574        }
575        uptree_t[n..]
576            .iter()
577            .map(|u| u.data.first().cloned().unwrap_or_else(Zero::zero))
578            .collect()
579    }

Source

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

Examples found in repository ?

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

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

Source

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

Examples found in repository ?

crates/competitive/src/math/formal_power_series/formal_power_series_impls.rs (lines 662-668)

657    pub fn sum_of_powers<I>(iter: I, deg: usize) -> Self
658    where
659        I: IntoIterator<Item = T>,
660    {
661        let mut n = T::zero();
662        let prod = Self::product_all(
663            iter.into_iter().map(|a| {
664                n += T::one();
665                Self::from_vec(vec![T::one(), -a])
666            }),
667            deg,
668        );
669        (-prod.log(deg).diff() << 1) + Self::from_vec(vec![n])
670    }

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 645-649)

640    pub fn linear_sum_of_exp<I, F>(iter: I, deg: usize, mut inv_fact: F) -> Self
641    where
642        I: IntoIterator<Item = (T, T)>,
643        F: FnMut(usize) -> T,
644    {
645        let (p, q) = Self::sum_all_rational(
646            iter.into_iter()
647                .map(|(a, b)| (Self::from_vec(vec![a]), Self::from_vec(vec![T::one(), -b]))),
648            deg,
649        );
650        let mut f = (p * q.inv(deg)).prefix(deg);
651        for i in 0..f.length() {
652            f[i] *= inv_fact(i);
653        }
654        f
655    }

Source

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

Examples found in repository ?

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

630    pub fn kth_term(a: Vec<T>, k: usize) -> T
631    where
632        C: NttReuse<T = Vec<T>>,
633    {
634        if let Some(x) = a.get(k) {
635            return x.clone();
636        }
637        Self::from_vec(berlekamp_massey(&a)).kth_term_of_linearly_recurrence(a, k)
638    }

More examples

Hide additional examples

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

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

Source

pub fn kth_term(a: Vec<T>, k: usize) -> T
where C: NttReuse<T = Vec<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

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

sum_i (a_i x)^j

Source §

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

Source

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

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

Examples found in repository ?

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

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

Source §

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

Source

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

Trait Implementations§

Source §

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

Source §

type Output = FormalPowerSeries<T, C>

The resulting type after applying the + operator.

Source §

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

Performs the + operation. Read more

Source §

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

Source §

type Output = FormalPowerSeries<T, C>

The resulting type after applying the + operator.

Source §

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

Performs the + operation. Read more

Source §

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

Source §

type Output = FormalPowerSeries<T, C>

The resulting type after applying the + operator.

Source §

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

Performs the + operation. Read more

Source §

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

Source §

type Output = FormalPowerSeries<T, C>

The resulting type after applying the + operator.

Source §

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

Performs the + operation. Read more

Source §

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

Source §

type Output = FormalPowerSeries<T, C>

The resulting type after applying the + operator.

Source §

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

Performs the + operation. Read more

Source §

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

Source §

type Output = FormalPowerSeries<T, C>

The resulting type after applying the + operator.

Source §

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

Performs the + operation. Read more

Source §

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

Source §

type Output = FormalPowerSeries<T, C>

The resulting type after applying the + operator.

Source §

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

Performs the + operation. Read more

Source §

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

Source §

type Output = FormalPowerSeries<T, C>

The resulting type after applying the + operator.

Source §

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

Performs the + operation. Read more

Source §

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

Source §

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

Performs the += operation. Read more

Source §

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

Source §

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

Performs the += operation. Read more

Source §

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

Source §

fn add_assign(&mut self, rhs: T)

Performs the += operation. Read more

Source §

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

Source §

fn add_assign(&mut self, rhs: Self)

Performs the += operation. Read more

Source §

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

Source §

fn clone(&self) -> Self

Returns a duplicate of the value. Read more

1.0.0 · Source§

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

Performs copy-assignment from source. Read more

Source §

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

Source §

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

Formats the value using the given formatter. Read more

Source §

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

Source §

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

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

Source §

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

Source §

type Output = FormalPowerSeries<T, C>

The resulting type after applying the / operator.

Source §

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

Performs the / operation. Read more

Source §

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

Source §

type Output = FormalPowerSeries<T, C>

The resulting type after applying the / operator.

Source §

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

Performs the / operation. Read more

Source §

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

Source §

type Output = FormalPowerSeries<T, C>

The resulting type after applying the / operator.

Source §

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

Performs the / operation. Read more

Source §

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

Source §

type Output = FormalPowerSeries<T, C>

The resulting type after applying the / operator.

Source §

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

Performs the / operation. Read more

Source §

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

Source §

type Output = FormalPowerSeries<T, C>

The resulting type after applying the / operator.

Source §

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

Performs the / operation. Read more

Source §

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

Source §

type Output = FormalPowerSeries<T, C>

The resulting type after applying the / operator.

Source §

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

Performs the / operation. Read more

Source §

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

Source §

type Output = FormalPowerSeries<T, C>

The resulting type after applying the / operator.

Source §

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

Performs the / operation. Read more

Source §

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

Source §

type Output = FormalPowerSeries<T, C>

The resulting type after applying the / operator.

Source §

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

Performs the / operation. Read more

Source §

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

Source §

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

Performs the /= operation. Read more

Source §

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

Source §

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

Performs the /= operation. Read more

Source §

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

Source §

fn div_assign(&mut self, rhs: T)

Performs the /= operation. Read more

Source §

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

Source §

fn div_assign(&mut self, rhs: Self)

Performs the /= operation. Read more

Source §

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

Source §

fn from(x: T) -> Self

Converts to this type from the input type.

Source §

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

Source §

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

Converts to this type from the input type.

Source §

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

Source §

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

Creates a value from an iterator. Read more

Source §

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

Source §

type Output = T

The returned type after indexing.

Source §

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

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

Source §

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

Source §

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

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

Source §

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

Source §

type Item = &'a T

The type of the elements being iterated over.

Source §

type IntoIter = Iter<'a, T>

Which kind of iterator are we turning this into?

Source §

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value. Read more

Source §

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

Source §

type Item = &'a mut T

The type of the elements being iterated over.

Source §

type IntoIter = IterMut<'a, T>

Which kind of iterator are we turning this into?

Source §

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value. Read more

Source §

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

Source §

type Item = T

The type of the elements being iterated over.

Source §

type IntoIter = IntoIter<T>

Which kind of iterator are we turning this into?

Source §

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value. Read more

Source §

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

Source §

type Output = FormalPowerSeries<T, C>

The resulting type after applying the * operator.

Source §

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

Performs the * operation. Read more

Source §

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

Source §

type Output = FormalPowerSeries<T, C>

The resulting type after applying the * operator.

Source §

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

Performs the * operation. Read more

Source §

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

Source §

type Output = FormalPowerSeries<T, C>

The resulting type after applying the * operator.

Source §

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

Performs the * operation. Read more

Source §

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

Source §

type Output = FormalPowerSeries<T, C>

The resulting type after applying the * operator.

Source §

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

Performs the * operation. Read more

Source §

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

Source §

type Output = FormalPowerSeries<T, C>

The resulting type after applying the * operator.

Source §

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

Performs the * operation. Read more

Source §

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

Source §

type Output = FormalPowerSeries<T, C>

The resulting type after applying the * operator.

Source §

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

Performs the * operation. Read more

Source §

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

Source §

type Output = FormalPowerSeries<T, C>

The resulting type after applying the * operator.

Source §

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

Performs the * operation. Read more

Source §

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

Source §

type Output = FormalPowerSeries<T, C>

The resulting type after applying the * operator.

Source §

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

Performs the * operation. Read more

Source §

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

Source §

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

Performs the *= operation. Read more

Source §

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

Source §

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

Performs the *= operation. Read more

Source §

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

Source §

fn mul_assign(&mut self, rhs: T)

Performs the *= operation. Read more

Source §

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

Source §

fn mul_assign(&mut self, rhs: Self)

Performs the *= operation. Read more

Source §

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

Source §

type Output = FormalPowerSeries<T, C>

The resulting type after applying the - operator.

Source §

fn neg(self) -> Self::Output

Performs the unary - operation. Read more

Source §

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

Source §

type Output = FormalPowerSeries<T, C>

The resulting type after applying the - operator.

Source §

fn neg(self) -> Self::Output

Performs the unary - operation. Read more

Source §

impl<T, C> One for FormalPowerSeries<T, C>
where T: PartialEq + One,

Source §

fn one() -> Self

Source §

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

Source §

fn set_one(&mut self)

Source §

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

Source §

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

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

1.0.0 · Source§

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

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

Source §

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

Source §

type Output = FormalPowerSeries<T, C>

The resulting type after applying the % operator.

Source §

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

Performs the % operation. Read more

Source §

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

Source §

type Output = FormalPowerSeries<T, C>

The resulting type after applying the % operator.

Source §

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

Performs the % operation. Read more

Source §

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

Source §

type Output = FormalPowerSeries<T, C>

The resulting type after applying the % operator.

Source §

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

Performs the % operation. Read more

Source §

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

Source §

type Output = FormalPowerSeries<T, C>

The resulting type after applying the % operator.

Source §

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

Performs the % operation. Read more

Source §

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

Source §

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

Performs the %= operation. Read more

Source §

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

Source §

fn rem_assign(&mut self, rhs: Self)

Performs the %= operation. Read more

Source §

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

Source §

type Output = FormalPowerSeries<T, C>

The resulting type after applying the << operator.

Source §

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

Performs the << operation. Read more

Source §

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

Source §

type Output = FormalPowerSeries<T, C>

The resulting type after applying the << operator.

Source §

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

Performs the << operation. Read more

Source §

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

Source §

fn shl_assign(&mut self, rhs: usize)

Performs the <<= operation. Read more

Source §

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

Source §

type Output = FormalPowerSeries<T, C>

The resulting type after applying the >> operator.

Source §

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

Performs the >> operation. Read more

Source §

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

Source §

type Output = FormalPowerSeries<T, C>

The resulting type after applying the >> operator.

Source §

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

Performs the >> operation. Read more

Source §

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

Source §

fn shr_assign(&mut self, rhs: usize)

Performs the >>= operation. Read more

Source §

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

Source §

type Output = FormalPowerSeries<T, C>

The resulting type after applying the - operator.

Source §

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

Performs the - operation. Read more

Source §

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

Source §

type Output = FormalPowerSeries<T, C>

The resulting type after applying the - operator.

Source §

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

Performs the - operation. Read more

Source §

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

Source §

type Output = FormalPowerSeries<T, C>

The resulting type after applying the - operator.

Source §

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

Performs the - operation. Read more

Source §

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

Source §

type Output = FormalPowerSeries<T, C>

The resulting type after applying the - operator.

Source §

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

Performs the - operation. Read more

Source §

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

Source §

type Output = FormalPowerSeries<T, C>

The resulting type after applying the - operator.

Source §

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

Performs the - operation. Read more

Source §

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

Source §

type Output = FormalPowerSeries<T, C>

The resulting type after applying the - operator.

Source §

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

Performs the - operation. Read more

Source §

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

Source §

type Output = FormalPowerSeries<T, C>

The resulting type after applying the - operator.

Source §

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

Performs the - operation. Read more

Source §

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

Source §

type Output = FormalPowerSeries<T, C>

The resulting type after applying the - operator.

Source §

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

Performs the - operation. Read more

Source §

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

Source §

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

Performs the -= operation. Read more

Source §

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

Source §

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

Performs the -= operation. Read more

Source §

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

Source §

fn sub_assign(&mut self, rhs: T)

Performs the -= operation. Read more

Source §

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

Source §

fn sub_assign(&mut self, rhs: Self)

Performs the -= operation. Read more

Source §

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

Source §

fn zero() -> Self

Source §

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

Source §

fn set_zero(&mut self)

Source §

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

Auto Trait Implementations§

§

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

§

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

§

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

§

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

§

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

§

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

Blanket Implementations§

Source §

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

Source §

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more

Source §

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

Source §

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more

Source §

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

Source §

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

Mutably borrows from an owned value. Read more

Source §

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

Source §

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

🔬This is a nightly-only experimental API. (clone_to_uninit)

Performs copy-assignment from self to dest. Read more

Source §

impl<T> From<!> for T

Source §

fn from(t: !) -> T

Converts to this type from the input type.

Source §

impl<T> From<T> for T

Source §

fn from(t: T) -> T

Returns the argument unchanged.

Source §

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

Source §

fn into(self) -> U

Calls U::from(self).

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

Source §

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

Source §

type Owned = T

The resulting type after obtaining ownership.

Source §

fn to_owned(&self) -> T

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

Source §

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

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

Source §

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

Source §

type Error = Infallible

The type returned in the event of a conversion error.

Source §

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

Performs the conversion.

Source §

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

Source §

type Error = >::Error

The type returned in the event of a conversion error.

Source §

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

Performs the conversion.

Struct FormalPowerSeries Copy item path

Fields§

Implementations§

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

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

pub fn length(&self) -> usize

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

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

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

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

pub fn zeros(deg: usize) -> Self

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

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

pub fn reversed(self) -> Self

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

pub fn coeff(&self, deg: usize) -> T

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

pub fn trim_tail_zeros(&mut self)

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

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

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

pub fn even(self) -> Self

pub fn odd(self) -> Self

pub fn diff(self) -> Self

pub fn integral(self) -> Self

pub fn parity_inversion(self) -> Self

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

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

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

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

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

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

fn pow_sparse1(&self, rhs: T, 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) -> Twhere C: NttReuse<T = Vec<T>>,

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

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

fn middle_product(self, other: &C::F, deg: usize) -> Self

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

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

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

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

pub fn kth_term(a: Vec<T>, k: usize) -> Twhere C: NttReuse<T = Vec<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,

pub fn sum_of_powers<I>(iter: I, deg: usize) -> Selfwhere I: IntoIterator<Item = 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)

Struct FormalPowerSeries

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

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

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 bostan_mori(self, rhs: Self, n: usize) -> T
where C: NttReuse<T = Vec<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 kth_term_of_linearly_recurrence(self, a: Vec<T>, k: usize) -> T
where C: NttReuse<T = Vec<T>>,

pub fn kth_term(a: Vec<T>, k: usize) -> T
where C: NttReuse<T = Vec<T>>,

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,

pub fn sum_of_powers<I>(iter: I, deg: usize) -> Self
where I: IntoIterator<Item = 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>>,