library_checker/math/
sharp_p_subset_sum.rs

1use competitive::prelude::*;
2#[doc(no_inline)]
3pub use competitive::{
4    math::{Fps998244353, MemorizedFactorial},
5    num::{One, Zero, montgomery::MInt998244353},
6};
7
8#[verify::library_checker("sharp_p_subset_sum")]
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}