[ABC358E] Alphabet Tiles
Link:Luogu - AT_abc358_e
题面翻译
题目描述
AtCoder Land 公司出售写有英文字母的瓷砖。高桥想把这些瓷砖排成一排,做成一个铭牌。
求长度在 1 1 1 和 K K K (包括 1 1 1 和 K K K )之间的由大写英文字母组成的字符串中,满足以下条件的字符串的个数(对 998244353 998244353 998244353 取模):
- 对于满足 1 ≤ i ≤ 26 1 \leq i \leq 26 1≤i≤26 的每个整数 i i i ,下面的条件成立:
- 设 a i a_i ai 是按词典顺序排列的 i i i 个大写英文字母。例如, a 1 = a_1 = a1=
a
, a 5 = a_5 = a5=E
, a 26 = a_{26} = a26=Z
. - 字符串中 a i a_i ai 的出现次数介于 0 0 0 和 C i C_i Ci 之间(包括首尾两次)。
- 设 a i a_i ai 是按词典顺序排列的 i i i 个大写英文字母。例如, a 1 = a_1 = a1=
输入格式
输入内容由标准输入法提供,格式如下
K K K
C 1 C_1 C1 C 2 C_2 C2 … \ldots … C 26 C_{26} C26
输出格式
满足条件的字符串的个数(对 998244353 998244353 998244353 取模)
数据范围
- 1 ≤ K ≤ 1000 1 \leq K \leq 1000 1≤K≤1000
- 0 ≤ C i ≤ 1000 0 \leq C_i \leq 1000 0≤Ci≤1000
- 所有输入值均为整数。
样例解释1
对于第一个样例,满足条件的 10 10 10 个字符串是 A
, B
, C
, AA
, AB
, AC
, BA
, BC
, CA
, CB
。
题目描述
AtCoder Land では、アルファベットの書かれたタイルが販売されています。高橋君は、タイルを一列に並べてネームプレートを作ろうと考えました。
長さ $ 1 $ 以上 $ K $ 以下の英大文字からなる文字列であって、以下の条件を満たすものの個数を $ 998244353 $ で割った余りを求めてください。
- $ 1\ \leq\ i\ \leq\ 26 $ を満たす任意の整数 $ i $ について以下が成立する。
- 辞書順で $ i $ 番目の英大文字を $ a_i $ とおく。例えば、$ a_1\ = $
A
, $ a_5\ = $E
, $ a_{26}\ = $Z
である。 - 文字列の中に含まれている $ a_i $ の個数は $ 0 $ 個以上 $ C_i $ 個以下である。
- 辞書順で $ i $ 番目の英大文字を $ a_i $ とおく。例えば、$ a_1\ = $
输入格式
入力は以下の形式で標準入力から与えられる。
$ K $ $ C_1 $ $ C_2 $ $ \ldots $ $ C_{26} $
输出格式
答えを出力せよ。
样例 #1
样例输入 #1
2
2 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
样例输出 #1
10
样例 #2
样例输入 #2
358
1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
样例输出 #2
64
样例 #3
样例输入 #3
1000
1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000
样例输出 #3
270274035
提示
制約
- $ 1\ \leq\ K\ \leq\ 1000 $
- $ 0\ \leq\ C_i\ \leq\ 1000 $
- 入力される値はすべて整数
Sample Explanation 1
A
, B
, C
, AA
, AB
, AC
, BA
, BC
, CA
, CB
の $ 10 $ 個の文字列が条件を満たします。
解题思路
这道题有点像“摆花”那道题(多重背包),其实就是在那题的基础上加了一个组合数
题意就可以变成:共有k个位置,其中第i种花有a[i]种,且前后顺序不定(与摆花的不同点),求前k个位置有多少种放法
我们找个例子模拟一下:k=3,a[1]=3,a[2]=2,a[3]=4
设f[i][j]表示前i种花,摆的花的个数为j的方案数:
从第一种花开始:
f[1][0]=1,f[1][1]=1,f[1][2]=1,f[1][3]=1(因为只有一个数,显然答案都是1)
然后第二种花:
f[2][0]=1
f[2][1]=2:当第二种花放0盆时,=f[1][1]=1;第二种花放1盆时,=1
f[2][2]=4:第二种花放0盆时,=f[1][2]=1;第二种花放1盆时,=f[1][1]*C(2,1)=2;第二种花放2盆时,=f[1][0]*C(2,2)=1;第二种花放3盆,不够
f[2][3]=7:第二种花放0盆时,=f[1][3]=1;第二种花放1盆时,=f[1][2]*C(3,1)=3;第二种花放2盆时,=f[1][1]*C(3,2)=3;第二种花放3盆,不够
………………
经过上面的模拟,我们已经摸清了题目的实现方法。直接用多重背包的转移即可。
本题中,dp[i][j]表示前i种字母,长度为j的方案数
dp方程: d p [ i ] [ j ] = ∑ k = 0 m i n ( a [ i ] , j ) d p [ i − 1 ] [ j − k ] × C j k dp[i][j]= \sum\limits_{k=0}^{min(a[i],j)} dp[i-1][j-k] \times C_j^k dp[i][j]=k=0∑min(a[i],j)dp[i−1][j−k]×Cjk
这里解释一下求组合数的方法:
以3个位置,a[1]=2,a[2]=1为例,我们可以先确定第二种花的位置,共有C(3,1)=3种可能;
然后,把第一种花往剩下的两个空里插,答案就是前1种花放2盆的方案数,即f[1][2]
两者相乘,即为总方案数。=f[1][2]*C(3,1) ······这是著名的排列组合方法:插点法
我们知道算组合数C的复杂度很高,可以用杨辉三角预处理。杨辉三角第i行第j列的值即为C(i,j)
解释一下:可以从杨辉三角递推式入手:f[i][j]=f[i-1][j]+f[i-1][j-1]
可以把f[i][j]看成前i个数,选j个数的组合数,则f[i-1][j]表示不选第i个数,转移要从前面选j个数的方案转移;
同理,f[i-1][j-1]就表示选第i个数,这样前i-1个数里要选j-1个数。因为是求方案数的dp,所以转移时要求和。
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxk = 1005;
const int mod = 998244353;
ll C[maxk][maxk];
int a[27]; // a[i]是题面中的c[i],避免与组合数的C混淆
ll dp[27][maxk];
void solve()
{
C[0][0] = 1;
for(int i = 1; i <= 1000; 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;
}
}
int K; cin >> K;
for(int i = 1; i <= 26; i ++) cin >> a[i];
dp[0][0] = 1; // 初始化:前0种花,选0个的方案数为1
for(int i = 1; i <= 26; i ++){
for(int j = 0; j <= K; j ++){ // 注意这里的K是输入的k
for(int k = 0; k <= min(a[i], j); k ++){ // 这里的k是枚举的k
dp[i][j] = (dp[i][j] + (dp[i - 1][j - k] * C[j][k]) % mod) % mod;
}
}
}
ll ans = 0; // 答案就是dp[26][1~k]的和
for(int i = 1; i <= K; i ++) ans = (ans + dp[26][i]) % mod;
cout << ans << '\n';
}
signed main()
{
ios :: sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
solve();
return 0;
}
End
这里是YLCHUP,谢谢大家!