题解：[ABC358E] Alphabet Tiles

[ABC358E] Alphabet Tiles

Link：Luogu - AT_abc358_e

题面翻译

题目描述

AtCoder Land 公司出售写有英文字母的瓷砖。高桥想把这些瓷砖排成一排，做成一个铭牌。

求长度在 $1$ 和 $K$ （包括 $1$ 和 $K$ ）之间的由大写英文字母组成的字符串中，满足以下条件的字符串的个数（对 $998244353$ 取模）：

• 对于满足 $1\le i\le 26$ 的每个整数 $i$ ，下面的条件成立：
  • 设 $a_i$ 是按词典顺序排列的 $i$ 个大写英文字母。例如， $a_1=$ a, $a_5=$ E, $a_{26}=$ Z.
  • 字符串中 $a_i$ 的出现次数介于 $0$ 和 $C_i$ 之间（包括首尾两次）。

输入格式

输入内容由标准输入法提供，格式如下

$K$

$C_1$ $C_2$ $\dots$ $C_{26}$

输出格式

满足条件的字符串的个数（对 $998244353$ 取模）

数据范围

• $1\le K\le 1000$
• $0\le C_i\le 1000$
• 所有输入值均为整数。

样例解释1

对于第一个样例，满足条件的 $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 $ 個以下である。

输入格式

入力は以下の形式で標準入力から与えられる。

$ 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 $ 個の文字列が条件を満たします。

解题思路

提示：需要掌握多重背包（文章1 文章2）、组合数学（计算方法 一些习题）的一些知识。

这道题有点像“摆花”那道题（多重背包），其实就是在那题的基础上加了一个组合数
题意就可以变成：共有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方程：$dp[i][j]=\sum _{k=0}^{min(a[i],j)}dp[i-1][j-k]\times C_j^k$

这里解释一下求组合数的方法：
以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，谢谢大家！