Alphabet Tiles の解説

同じ問題: https://atcoder.jp/contests/abc234/tasks/abc234_f

dp[i][j] := i番目までの文字列を使って作れる長さjの文字列の個数

としてdpする。

遷移として、次の文字cをp個使う時を考える。

その場合、文字列の長さはj + pになるが、この中で、pを置く場所の通りは

$$\binom{j + p}{p}$$

ですので、これを用いて、遷移してあげればよい。

fn main() {
    input! {
        k: usize,
        c: [usize; 26]
    }
    let mut dp = vec![vec![ModInt998244353::new(0); k + 1]; 26 + 1];
    dp[0][0] += 1usize;

    let nck = Comb::<ModInt998244353>::new(k + 10);

    for i in 0..26 {
        for j in 0..=k {
            if dp[i][j].val() == 0 {
                continue;
            }
            let now = dp[i][j];
            let maxnum = c[i];
            for num in 0..=maxnum {
                let next = j + num;
                if next > k {
                    continue;
                }
                dp[i + 1][next] += now * nck.nck(j + num, num);
            }
        }
    }
    let ans = dp[26].iter().sum::<ModInt998244353>();
    println!("{}",ans - 1);
}