E - Alphabet Tiles

キーワード

解説

DP で解く。

$0 \le i \le 26, 0 \le j \le 1000$ に対して、 $dp_{i,j}$ を以下のように定義する。

$i$ 番目のアルファベットを使って、長さ $j$ の文字列を作る方法の数

このとき、 $i$ 文字目を $l$ 回使う場合の数は以下のようになる。

dp_{i-1,j-l} \times \frac{j!}{l!(j-l)!}

ここで、 $i$ 文字目は $C_i$ 回使えるので、 $l$ は $0 \le l \le \min(j,C_i)$ である。

$0 \le i \le 26, 0 \le j \le 1000$ に対して、次のように $dp$ を更新する。

$i = 0$ のとき: $dp_{0,0} = 1$ , それ以外は $0$
$i > 0$ のとき: $dp_{i,j} = \sum_{l=0}^{\min(j,C_i)} dp_{i-1,j-l} \times \frac{j!}{l!(j-l)!}$

最後に、 $1 <= j <= K$ に対して、 $dp_{26,j}$ の総和を求める。空文字列は含まないので、 $j = 0$ は含めないことに注意する。

制約から、 $0 \le j,l \le 1000$ より、階乗や逆元の計算は前計算しておくとよい。

提出コード

const MOD = 998244353
 
func main() {
	k := readInt()
	C := readInts()
 
	frac := make([]int, 1001)
	frac[0] = 1
	for i := 1; i < 1001; i++ {
		frac[i] = frac[i-1] * i % MOD
	}
 
	inv := make([]int, 1001)
	for i := 0; i < 1001; i++ {
		inv[i] = modPow(frac[i], MOD-2, MOD)
	}
 
	DP := make([][]int, 27)
	for i := 0; i < 27; i++ {
		DP[i] = make([]int, 1001)
	}
	DP[0][0] = 1
	for i := 1; i < 27; i++ {
		for j := 0; j <= k; j++ {
			for l := 0; l <= min(j, C[i-1]); l++ {
				DP[i][j] += DP[i-1][j-l] * ((frac[j] * inv[l] % MOD) * inv[j-l] % MOD)
				DP[i][j] %= MOD
			}
		}
	}
	ans := 0
	for i := 1; i <= k; i++ {
		ans += DP[26][i]
		ans %= MOD
	}
	writeLine(ans)
}

#define MOD 998244353
#define MAX 10001
 
ll modpow(ll a, ll n) {
    ll res = 1;
    while(n > 0) {
        if(n & 1) res = res * a % MOD;
        a = a * a % MOD;
        n >>= 1;
    }
    return res;
}
 
int main() {
    ll k; cin >> k;
    vector<ll> C(26); rep(i, 0, 26) cin >> C[i];
 
    vector<ll> frac(MAX), inv(MAX);
    frac[0] = 1;
    rep(i, 1, MAX) frac[i] = frac[i-1] * i % MOD;
    rep(i, 0, MAX) inv[i] = modpow(frac[i], MOD-2);
 
    vector<vector<ll>> dp(27,vector<ll>(MAX,0));
    dp[0][0] = 1;
    rep(i, 1, 27) {
        rep(j, 0, k+1) {
            rep(l, 0, min(j,C[i-1])+1) {
                dp[i][j] += dp[i-1][j-l] * ((frac[j] * inv[l] % MOD) * inv[j-l] % MOD);
                dp[i][j] %= MOD;
            }
        }
    }
    ll ans = 0;
    rep(i, 1, k+1) {
        ans += dp[26][i];
        ans %= MOD;
    }
    cout << ans << endl;
}

D - Souvenirs 359