Skip to main content

library_checker/enumerative_combinatorics/
sharp_p_subset_sum.rs

1use competitive::prelude::*;
2use competitive::{
3    math::{Fps998244353, MemorizedFactorial},
4    num::{One, Zero, montgomery::MInt998244353 as M},
5};
6
7#[verify::library_checker("sharp_p_subset_sum")]
8pub fn sharp_p_subset_sum(reader: impl Read, writer: impl Write) {
9    prepare_io!(reader, writer);
10    sc!(n, t, s: [usize; iter n]);
11    let f = MemorizedFactorial::new(t);
12    let mut c = vec![M::zero(); t + 1];
13    for s in s {
14        c[s] += M::one();
15    }
16    let a = Fps998244353::from_vec(c).count_subset_sum(t + 1, |x| f.inv(x));
17    pp!(@it a.data[1..]);
18}