AtCoder ~ E - Alphabet Tiles
Luogu ~ ABC358E Alphabet Tiles
题意简述
给定正整数 \(K\) 和 \(C_1,C_2,\dots,C_{26}\)。请求出长度在 \(1\) 到 \(K\) 之间，满足下列条件的字符串个数（取模 \(998244353\)）：
- 该字符串全由大写字母组成。
- 对于 \(1\le i\le 26\)，下面条件成立：
- 设 \(a_i\) 为第 \(i\) 个大写字母，比如 \(a_5=\)
E。 - 该字符串中，\(a_i\) 出现的次数不超过 \(C_i\)。
- 设 \(a_i\) 为第 \(i\) 个大写字母，比如 \(a_5=\)
解题思路
我们考虑dp。设 \(f[i][j]\) 为用前 \(i\) 种字母，组成长度为 \(j\) 的字符串个数。
归纳得出，“前 \(i\) 种字母，组成长度为 \(j\)”，就相当于下面几种情况求和：
- 前 \(i-1\) 种字母，组成长度为 \(j\)。
- 前 \(i-1\) 种字母，组成长度为 \(j-1\)，再在中间插入 \(1\) 个字母 \(i\)。
- \(\dots\)
- 前 \(i-1\) 种字母，组成长度为 \(j-s\)，再在中间插入 \(t\) 个字母 \(i\)。
其中 \(t=\min(j,c[i])\)。
从而得到状态转移方程：
\(f[i][j]=\sum\limits_{s=0}^{\min(j,c[i])}f[i-1][j-s]*C_j^s\)。
（解释：\(j\)的长度中，先取出\(s\)个位置放字母\(i\)，剩下位置就是字母\(1\sim (i-1)\)组成的长度为\(j\)的字符串了）
初始值：\(f[i][0]=1\)。
时间复杂度：\(C\)需要\(O(k^2)\)预处理，dp过程\(O(26*k^2)\)。总时间复杂度\(O(26*k^2)\)。
空间复杂度：\(O(26*k)\)，但可以滚动数组变成\(O(k)\)。
Code
非滚动数组
#include<bits/stdc++.h>
#define int long long
#define mod 998244353
using namespace std;
int k,c[30],C[1010][1010];
int f[30][1010];
int ans;
signed main(){
cin>>k;
for(int i=0;i<=k;i++){
C[i][0]=C[i][i]=1;
for(int j=1;j<i;j++)
C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
}
for(int i=1;i<=26;i++) cin>>c[i];
for(int i=0;i<=26;i++) f[i][0]=1;
for(int i=1;i<=26;i++)
for(int j=1;j<=k;j++)
for(int s=0;s<=min(j,c[i]);s++)
f[i][j]=(f[i][j]+(f[i-1][j-s]*C[j][s]%mod))%mod;
for(int i=1;i<=k;i++) ans=(ans+f[26][i])%mod;
cout<<ans;
return 0;
}
滚动数组
#include<bits/stdc++.h>
#define int long long
#define mod 998244353
using namespace std;
int k,c[30],C[1010][1010];
int f[1010];
int ans;
signed main(){
cin>>k;
for(int i=0;i<=k;i++){
C[i][0]=C[i][i]=1;
for(int j=1;j<i;j++)
C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
}
for(int i=1;i<=26;i++) cin>>c[i];
f[0]=1;
for(int i=1;i<=26;i++)
for(int j=k;j>=1;j--)//注意倒序枚举
for(int s=1;s<=min(j,c[i]);s++)
//不从0开始是因为已经有值了
f[j]=(f[j]+(f[j-s]*C[j][s]%mod))%mod;
for(int i=1;i<=k;i++) ans=(ans+f[i])%mod;
cout<<ans;
return 0;
}