competitive/math/formal_power_series/
mod.rs

1use super::{
2    Convolve998244353, ConvolveSteps, MInt, MIntConvert, MIntConvolve, MemorizedFactorial,
3    NttReuse, One, 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    type Base: MIntConvert<usize>;
55    fn pow(self, exp: usize) -> Self;
56    fn memorized_factorial(n: usize) -> MemorizedFactorial<Self::Base> {
57        MemorizedFactorial::new(n)
58    }
59    fn memorized_inv(mf: &MemorizedFactorial<Self::Base>, n: usize) -> Self;
60}
61
62impl<M> FormalPowerSeriesCoefficient for MInt<M>
63where
64    M: MIntConvert<usize>,
65{
66    type Base = M;
67    fn pow(self, exp: usize) -> Self {
68        Self::pow(self, exp)
69    }
70    fn memorized_inv(mf: &MemorizedFactorial<Self::Base>, n: usize) -> Self {
71        mf.inv(n)
72    }
73}
74
75pub trait FormalPowerSeriesCoefficientSqrt: FormalPowerSeriesCoefficient {
76    fn sqrt_coefficient(&self) -> Option<Self>;
77}
78
79impl<M> FormalPowerSeriesCoefficientSqrt for MInt<M>
80where
81    M: MIntConvert<u32> + MIntConvert<usize>,
82{
83    fn sqrt_coefficient(&self) -> Option<Self> {
84        self.sqrt()
85    }
86}
87
88mod formal_power_series_impls;
89mod formal_power_series_nums;
competitive/math/formal_power_series/mod.rs

competitive/math/formal_power_series/
mod.rs
