题解：AT_abc358_e [ABC358E] Alphabet Tiles

ylch · 2024-07-20 11:19:33 · 题解

[ABC358E] Alphabet Tiles

Link：Luogu - AT_abc358_e

题面翻译

题目描述

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

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

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

输入格式

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

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

输出格式

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

数据范围

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

样例解释1

对于第一个样例，满足条件的 10 个字符串是 A, B, C, AA, AB, AC, BA, BC, CA, CB。

题目描述

AtCoder Land では、アルファベットの書かれたタイルが販売されています。高橋君は、タイルを一列に並べてネームプレートを作ろうと考えました。

長さ 1 以上 K 以下の英大文字からなる文字列であって、以下の条件を満たすものの個数を 998244353 で割った余りを求めてください。

- 辞書順で $ 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

样例 #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

样例 #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[2][0]=1

- 第二种花放 $0$ 盆时,$=f[1][1]=1$； - 第二种花放 $1$ 盆时,$=1

- 第二种花放 $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\limits_{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，所以转移时要求和。

AC 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，谢谢大家！

广告：本文同步发布到 csdn博客