AtCoder Beginner Contest 433 F

https://atcoder.jp/contests/abc433/tasks/abc433_f

簡単な例から考えましょう。例えば、1111222とします。
1文字だけ取るとすると、4つある1から1つ、3つある2から1つ取るときの場合の数は、2つずつ取るときの場合の数は、3つ取るときはです。乗数のCの右側をひっくり返すと、

なので、これはのの係数からを引いたものになるから、となります。

次に、113311221122を考えます。1と2で考えると、それ以外の文字は無視して、1が4つ、2が2つ、1が2つ、2が2つとなります。そうしたときに、最初の2のブロックを必ず使う場合の数は、全部の2のブロックを使う場合の数から最初以外の2のブロックを使う場合の数を引けばいいから、となります。

// 1122 Subsequence 2
#![allow(non_snake_case)]


//////////////////// 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()
}

// ax = by + 1 (a, b > 0)
fn linear_diophantine(a: i64, b: i64) -> Option<(i64, i64)> {
    if a == 1 {
        return Some((1, 0))
    }
    
    let q = b / a;
    let r = b % a;
    if r == 0 {
        return None
    }
    let (x1, y1) = linear_diophantine(r, a)?;
    Some((-q * x1 - y1, -x1))
}

fn inverse<const D: i64>(a: i64) -> i64 {
    let (x, _y) = linear_diophantine(a, D).unwrap();
    x.rem_euclid(D)
}


//////////////////// CombinationCalculator ////////////////////

struct CombinationCalculator<const D: i64> {
    facts: Vec<i64>
}

impl<const D: i64> CombinationCalculator<D> {
    // nCm
    fn apply(&self, n: i64, m: i64) -> i64 {
        let num = self.facts[n as usize];
        let den = self.facts[m as usize] * self.facts[(n-m) as usize] % D;
        num * inverse::<D>(den) % D
    }
    
    fn create(N: usize) -> CombinationCalculator::<D> {
        let mut facts: Vec<i64> = vec![1; N+1];
        for n in 1..N+1 {
            facts[n] = facts[n-1] * (n as i64) % D
        }
        CombinationCalculator::<D> { facts }
    }
}


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

const D: i64 = 998244353;

fn groupby(d: u8, ds: &Vec<u8>) -> Vec<i64> {
    // d = 0なら0が何個、1が何個、…というデータを作る
    let mut ls: Vec<i64> = vec![];
    let mut len: i64 = 0;
    for &d1 in ds.iter() {
        let d_cur  = if ls.len() % 2 == 0 { d } else { d + 1 };
        let d_next = if ls.len() % 2 == 1 { d } else { d + 1 };
        if d1 == d_cur {
            len += 1
        }
        else if d1 == d_next {
            ls.push(len);
            len = 1
        }
    }
    if ls.len() % 2 == 1 {
        ls.push(len)
    }
    ls
}

fn F_each(d: u8, ds: &Vec<u8>, cc: &CombinationCalculator::<D>) -> i64 {
    let ls = groupby(d, ds);
    let mut num_l1: i64 = 0;
    let mut num_l2 = (1..ls.len()).step_by(2).map(|i| ls[i]).sum::<i64>();
    let mut s: i64 = 0;
    for i in (0..ls.len()).step_by(2) {
        let l1 = ls[i];
        let l2 = ls[i+1];
        num_l1 += l1;
        num_l2 -= l2;
        s = (s + cc.apply(num_l1+num_l2+l2, num_l1) -
                 cc.apply(num_l1+num_l2, num_l1)).rem_euclid(D)
    }
    s
}

fn F(S: String) -> i64 {
    let ds: Vec<u8> = S.chars().map(|c| c as u8 - ('0' as u8)).collect();
    let cc = CombinationCalculator::<D>::create(S.len());
    let mut s: i64 = 0;
    for d in 0..9 {
        s += F_each(d, &ds, &cc)
    }
    s % D
}

fn main() {
    let S: String = read();
    println!("{}", F(S))
}