题解：AT_abc358_e [ABC358E] Alphabet Tiles

· · 题解

diff：1397。

神奇 dp 题。

看到这个题，让计数，计数的题大多都是数学题和 dp 题，那我们往 dp 方面想。

设 dp_{i,j} 表示前 i 个字母组成长度为 j 的字符串的方案数，可以得出转移方程：

dp_{i+1,j}=\sum_{k=0}^{\min(j,c_{i+1})}C_j^k\times dp_{i,j-k}

组合数可以通过杨辉三角预处理求得，时间复杂度 O(\alpha k^2)，其中 \alpha 是字母表大小，为 26。

#include<bits/stdc++.h>
#define N 1005
#define int long long
using namespace std;
const int mod=998244353;
int C[N][N],k,c[N],dp[N][N],ans;
signed main(){
    C[0][0]=1;
    for(int i=1;i<N;++i){
        C[i][0]=1;
        for(int j=1;j<=i;++j){
            C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
        }
    }
    cin>>k;
    for(int i=1;i<=26;++i)cin>>c[i];
    dp[0][0]=1;
    for(int i=0;i<26;++i){
        for(int j=0;j<=k;++j){
            for(int l=0;l<=min(j,c[i+1]);++l){
                dp[i+1][j]=(dp[i+1][j]+dp[i][j-l]*C[j][l])%mod;
            }
        }
    }
    for(int i=1;i<=k;++i)ans=(ans+dp[26][i])%mod;
    cout<<ans; 
    return 0;
}