Struct MemorizedFactorial

Source

pub struct MemorizedFactorial<M>where
    M: MIntConvert<usize>,{
    pub fact: Vec<MInt<M>>,
    pub inv_fact: Vec<MInt<M>>,
}

Fields§

§fact: Vec<MInt<M>>§inv_fact: Vec<MInt<M>>

Implementations§

Source §

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

Source

pub fn new(max_n: usize) -> Self

Examples found in repository ?

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

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}

More examples

Hide additional examples

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

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}

crates/competitive/src/math/mint_matrix.rs (line 97)

89fn taylor_shift<M>(f: Vec<MInt<M>>, a: MInt<M>) -> Vec<MInt<M>>
90where
91    M: MIntConvert<usize>,
92{
93    let n = f.len();
94    if n == 0 {
95        return f;
96    }
97    let mf = MemorizedFactorial::new(n);
98    let mut res = vec![MInt::<M>::zero(); n];
99    let mut apow = vec![MInt::<M>::one(); n];
100    for i in 1..n {
101        apow[i] = apow[i - 1] * a;
102    }
103    for j in 0..n {
104        if f[j].is_zero() {
105            continue;
106        }
107        for k in 0..=j {
108            res[k] += f[j] * apow[j - k] * mf.combination(j, k);
109        }
110    }
111    res
112}

Source

pub fn combination(&self, n: usize, r: usize) -> MInt<M>

Examples found in repository ?

crates/competitive/src/math/factorial.rs (line 54)

49    pub fn homogeneous_product(&self, n: usize, r: usize) -> MInt<M> {
50        debug_assert!(n + r < self.fact.len() + 1);
51        if n == 0 && r == 0 {
52            MInt::one()
53        } else {
54            self.combination(n + r - 1, r)
55        }
56    }

More examples

Hide additional examples

crates/competitive/src/math/mint_matrix.rs (line 108)

89fn taylor_shift<M>(f: Vec<MInt<M>>, a: MInt<M>) -> Vec<MInt<M>>
90where
91    M: MIntConvert<usize>,
92{
93    let n = f.len();
94    if n == 0 {
95        return f;
96    }
97    let mf = MemorizedFactorial::new(n);
98    let mut res = vec![MInt::<M>::zero(); n];
99    let mut apow = vec![MInt::<M>::one(); n];
100    for i in 1..n {
101        apow[i] = apow[i - 1] * a;
102    }
103    for j in 0..n {
104        if f[j].is_zero() {
105            continue;
106        }
107        for k in 0..=j {
108            res[k] += f[j] * apow[j - k] * mf.combination(j, k);
109        }
110    }
111    res
112}

Source

pub fn permutation(&self, n: usize, r: usize) -> MInt<M>

Source

pub fn homogeneous_product(&self, n: usize, r: usize) -> MInt<M>

Source

pub fn inv(&self, n: usize) -> MInt<M>

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}