competitive/math/formal_power_series/
mod.rs

1use super::{
2    Convolve998244353, ConvolveSteps, MInt, MIntConvert, MIntConvolve, MemorizedFactorial, One,
3    PartialIgnoredOrd, Zero, berlekamp_massey, montgomery::MInt998244353,
4};
5use std::{
6    fmt::{self, Debug},
7    marker::PhantomData,
8    ops::{Add, AddAssign, Div, DivAssign, Mul, MulAssign, Neg, Sub, SubAssign},
9};
10
11#[derive(Default)]
12pub struct FormalPowerSeries<T, C> {
13    pub data: Vec<T>,
14    _marker: PhantomData<C>,
15}
16
17impl<T, C> Debug for FormalPowerSeries<T, C>
18where
19    T: Debug,
20{
21    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
22        Debug::fmt(&self.data, f)
23    }
24}
25
26pub type Fps998244353 = FormalPowerSeries<MInt998244353, Convolve998244353>;
27pub type Fps<M> = FormalPowerSeries<MInt<M>, MIntConvolve<M>>;
28
29pub trait FormalPowerSeriesCoefficient:
30    Sized
31    + Clone
32    + Zero
33    + PartialEq
34    + One
35    + From<usize>
36    + Add<Output = Self>
37    + Sub<Output = Self>
38    + Mul<Output = Self>
39    + Div<Output = Self>
40    + for<'r> Add<&'r Self, Output = Self>
41    + for<'r> Sub<&'r Self, Output = Self>
42    + for<'r> Mul<&'r Self, Output = Self>
43    + for<'r> Div<&'r Self, Output = Self>
44    + AddAssign<Self>
45    + SubAssign<Self>
46    + MulAssign<Self>
47    + DivAssign<Self>
48    + for<'r> AddAssign<&'r Self>
49    + for<'r> SubAssign<&'r Self>
50    + for<'r> MulAssign<&'r Self>
51    + for<'r> DivAssign<&'r Self>
52    + Neg<Output = Self>
53{
54}
55
56impl<M> FormalPowerSeriesCoefficient for MInt<M> where M: MIntConvert<usize> {}
57
58pub trait FormalPowerSeriesCoefficientSqrt: FormalPowerSeriesCoefficient {
59    fn sqrt_coefficient(&self) -> Option<Self>;
60}
61
62impl<M> FormalPowerSeriesCoefficientSqrt for MInt<M>
63where
64    M: MIntConvert<u32> + MIntConvert<usize>,
65{
66    fn sqrt_coefficient(&self) -> Option<Self> {
67        self.sqrt()
68    }
69}
70
71mod formal_power_series_impls;
72mod formal_power_series_nums;
competitive/math/formal_power_series/mod.rs

competitive/math/formal_power_series/
mod.rs
