pub trait FormalPowerSeriesCoefficient:
Sized
+ Clone
+ Zero
+ PartialEq
+ One
+ From<usize>
+ Add<Output = Self>
+ Sub<Output = Self>
+ Mul<Output = Self>
+ Div<Output = Self>
+ for<'r> Add<&'r Self, Output = Self>
+ for<'r> Sub<&'r Self, Output = Self>
+ for<'r> Mul<&'r Self, Output = Self>
+ for<'r> Div<&'r Self, Output = Self>
+ AddAssign<Self>
+ SubAssign<Self>
+ MulAssign<Self>
+ DivAssign<Self>
+ for<'r> AddAssign<&'r Self>
+ for<'r> SubAssign<&'r Self>
+ for<'r> MulAssign<&'r Self>
+ for<'r> DivAssign<&'r Self>
+ Neg<Output = Self> {
type Base: MIntConvert<usize>;
// Required methods
fn pow(self, exp: usize) -> Self;
fn memorized_inv(mf: &MemorizedFactorial<Self::Base>, n: usize) -> Self;
// Provided method
fn memorized_factorial(n: usize) -> MemorizedFactorial<Self::Base> { ... }
}Required Associated Types§
type Base: MIntConvert<usize>
Required Methods§
fn pow(self, exp: usize) -> Self
fn memorized_inv(mf: &MemorizedFactorial<Self::Base>, n: usize) -> Self
Provided Methods§
Sourcefn memorized_factorial(n: usize) -> MemorizedFactorial<Self::Base>
fn memorized_factorial(n: usize) -> MemorizedFactorial<Self::Base>
Examples found in repository?
crates/competitive/src/math/formal_power_series/formal_power_series_impls.rs (line 305)
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 }Dyn Compatibility§
This trait is not dyn compatible.
In older versions of Rust, dyn compatibility was called "object safety", so this trait is not object safe.