AtCoder Beginner Contest 321 F

https://atcoder.jp/contests/abc321/tasks/abc321_f

この手の場合の数は母関数です。

として、の係数が場合の数です。
このコードだと、下9桁を答えるでも成り立ちますね。

// #(subset sum = K) with Add and Erase
#![allow(non_snake_case)]


//////////////////// constants ////////////////////

const D: i64 = 998244353;


//////////////////// library ////////////////////

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
            .map(|e| e.parse().ok().unwrap()).collect()
}


//////////////////// process ////////////////////

fn read_input() -> (usize, usize) {
    let v = read_vec();
    let (Q, K) = (v[0], v[1]);
    (Q, K)
}

fn read_query() -> (bool, usize) {
    let v: Vec<String> = read_vec();
    (v[0] == "+", v[1].parse().unwrap())
}

fn mul(n: usize, p: Vec<i64>) -> Vec<i64> {
    let mut q = p.to_vec();
    for k in n..p.len() {
        q[k] += p[k-n];
        if q[k] >= D {
            q[k] -= D
        }
    }
    q
}

fn div(n: usize, p: Vec<i64>) -> Vec<i64> {
    let mut q = p.to_vec();
    for k in n..p.len() {
        q[k] -= q[k-n];
        if q[k] < 0 {
            q[k] += D
        }
    }
    q
}

fn F(Q: usize, K: usize) {
    let mut p = vec![0; K+1];
    p[0] = 1;
    for _ in 0..Q {
        p = match read_query() {
                (true, x)  => mul(x, p),
                (false, x) => div(x, p)
        };
        println!("{}", p[K])
    }
}

fn main() {
    let (Q, K) = read_input();
    F(Q, K)
}