Struct BinomialPrefixSum

Source

pub struct BinomialPrefixSum<M>where
    M: MIntConvert<usize>,{
    query: Vec<(usize, usize)>,
    _marker: PhantomData<fn() -> M>,
}

Fields§

§query: Vec<(usize, usize)>§_marker: PhantomData<fn() -> M>

Implementations§

Source §

impl<M> BinomialPrefixSum<M>
where M: MIntConvert<usize>,

Source

pub fn new() -> Self

Source

pub fn with_capacity(capacity: usize) -> Self

Examples found in repository ?

crates/competitive/src/math/binomial_prefix_sum.rs (line 148)

144    pub fn for_each_contribution<F>(self, mut f: F)
145    where
146        F: FnMut(usize, MInt<M>),
147    {
148        let mut binom = BinomialPrefixSum::<M>::with_capacity(self.query.len() * K);
149        let mut derived = Vec::with_capacity(self.query.len() * K);
150        let mut stirling = [[MInt::<M>::zero(); K]; K];
151        if K > 0 {
152            stirling[0][0] = MInt::one();
153        }
154        for n in 1..K {
155            for r in 1..=n {
156                stirling[n][r] = stirling[n - 1][r - 1] + MInt::from(r) * stirling[n - 1][r];
157            }
158        }
159        let mut coef_cache = HashMap::with_capacity(self.query.len());
160        for (i, (n, m, coef)) in self.query.iter().enumerate() {
161            let (n, m) = (*n, *m);
162            let coef = *coef_cache.entry(*coef).or_insert_with(|| {
163                let mut falling = [MInt::<M>::zero(); K];
164                for (k, &c) in coef.iter().enumerate() {
165                    if c.is_zero() {
166                        continue;
167                    }
168                    for r in 0..=k {
169                        falling[r] += c * stirling[k][r];
170                    }
171                }
172                falling
173            });
174            let mut falling = MInt::one();
175            for (r, &coef) in coef.iter().enumerate() {
176                if r > n || r > m {
177                    break;
178                }
179                if !coef.is_zero() {
180                    binom.push(n - r, m - r);
181                    derived.push((i, coef * falling));
182                }
183                if r + 1 < K {
184                    falling *= MInt::from(n - r);
185                }
186            }
187        }
188        binom.for_each(|i, x| {
189            let (q, coef) = derived[i];
190            f(q, coef * x);
191        });
192    }

Source

pub fn push(&mut self, n: usize, m: usize) -> usize

Examples found in repository ?

crates/competitive/src/math/binomial_prefix_sum.rs (line 180)

144    pub fn for_each_contribution<F>(self, mut f: F)
145    where
146        F: FnMut(usize, MInt<M>),
147    {
148        let mut binom = BinomialPrefixSum::<M>::with_capacity(self.query.len() * K);
149        let mut derived = Vec::with_capacity(self.query.len() * K);
150        let mut stirling = [[MInt::<M>::zero(); K]; K];
151        if K > 0 {
152            stirling[0][0] = MInt::one();
153        }
154        for n in 1..K {
155            for r in 1..=n {
156                stirling[n][r] = stirling[n - 1][r - 1] + MInt::from(r) * stirling[n - 1][r];
157            }
158        }
159        let mut coef_cache = HashMap::with_capacity(self.query.len());
160        for (i, (n, m, coef)) in self.query.iter().enumerate() {
161            let (n, m) = (*n, *m);
162            let coef = *coef_cache.entry(*coef).or_insert_with(|| {
163                let mut falling = [MInt::<M>::zero(); K];
164                for (k, &c) in coef.iter().enumerate() {
165                    if c.is_zero() {
166                        continue;
167                    }
168                    for r in 0..=k {
169                        falling[r] += c * stirling[k][r];
170                    }
171                }
172                falling
173            });
174            let mut falling = MInt::one();
175            for (r, &coef) in coef.iter().enumerate() {
176                if r > n || r > m {
177                    break;
178                }
179                if !coef.is_zero() {
180                    binom.push(n - r, m - r);
181                    derived.push((i, coef * falling));
182                }
183                if r + 1 < K {
184                    falling *= MInt::from(n - r);
185                }
186            }
187        }
188        binom.for_each(|i, x| {
189            let (q, coef) = derived[i];
190            f(q, coef * x);
191        });
192    }

Source

pub fn for_each<F>(self, f: F)
where F: FnMut(usize, MInt<M>),

Examples found in repository ?

crates/competitive/src/math/binomial_prefix_sum.rs (line 90)

88    pub fn solve(self) -> Vec<MInt<M>> {
89        let mut ans = vec![MInt::zero(); self.query.len()];
90        self.for_each(|i, x| ans[i] = x);
91        ans
92    }
93}
94
95pub struct BinomialPolynomialPrefixSum<M, const K: usize>
96where
97    M: MIntConvert<usize>,
98{
99    query: Vec<(usize, usize, [MInt<M>; K])>,
100}
101
102impl<M, const K: usize> Debug for BinomialPolynomialPrefixSum<M, K>
103where
104    M: MIntConvert<usize>,
105{
106    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
107        f.debug_struct("BinomialPolynomialPrefixSum")
108            .field("query", &self.query)
109            .finish()
110    }
111}
112
113impl<M, const K: usize> Default for BinomialPolynomialPrefixSum<M, K>
114where
115    M: MIntConvert<usize>,
116{
117    fn default() -> Self {
118        Self {
119            query: Default::default(),
120        }
121    }
122}
123
124impl<M, const K: usize> BinomialPolynomialPrefixSum<M, K>
125where
126    M: MIntConvert<usize>,
127{
128    pub fn new() -> Self {
129        Default::default()
130    }
131
132    pub fn with_capacity(capacity: usize) -> Self {
133        Self {
134            query: Vec::with_capacity(capacity),
135        }
136    }
137
138    pub fn push(&mut self, n: usize, m: usize, coef: [MInt<M>; K]) -> usize {
139        let q = self.query.len();
140        self.query.push((n, m, coef));
141        q
142    }
143
144    pub fn for_each_contribution<F>(self, mut f: F)
145    where
146        F: FnMut(usize, MInt<M>),
147    {
148        let mut binom = BinomialPrefixSum::<M>::with_capacity(self.query.len() * K);
149        let mut derived = Vec::with_capacity(self.query.len() * K);
150        let mut stirling = [[MInt::<M>::zero(); K]; K];
151        if K > 0 {
152            stirling[0][0] = MInt::one();
153        }
154        for n in 1..K {
155            for r in 1..=n {
156                stirling[n][r] = stirling[n - 1][r - 1] + MInt::from(r) * stirling[n - 1][r];
157            }
158        }
159        let mut coef_cache = HashMap::with_capacity(self.query.len());
160        for (i, (n, m, coef)) in self.query.iter().enumerate() {
161            let (n, m) = (*n, *m);
162            let coef = *coef_cache.entry(*coef).or_insert_with(|| {
163                let mut falling = [MInt::<M>::zero(); K];
164                for (k, &c) in coef.iter().enumerate() {
165                    if c.is_zero() {
166                        continue;
167                    }
168                    for r in 0..=k {
169                        falling[r] += c * stirling[k][r];
170                    }
171                }
172                falling
173            });
174            let mut falling = MInt::one();
175            for (r, &coef) in coef.iter().enumerate() {
176                if r > n || r > m {
177                    break;
178                }
179                if !coef.is_zero() {
180                    binom.push(n - r, m - r);
181                    derived.push((i, coef * falling));
182                }
183                if r + 1 < K {
184                    falling *= MInt::from(n - r);
185                }
186            }
187        }
188        binom.for_each(|i, x| {
189            let (q, coef) = derived[i];
190            f(q, coef * x);
191        });
192    }