1)题目意思
有 N 场比赛,比赛类型按顺序给成一个长度为 N 的字符串 S,只包含 A 到 J(一共 10 种类型)。
你要从这 N 场比赛中选出至少一场去参加(等价于选择一些下标,保持原顺序形成一个子序列)。
要求选出来的子序列满足:
同一种类型在子序列中出现时,必须是连续的一段,不能出现“分开又回来”的情况。
例如子序列类型是 B G B 就不合法,因为 B 被 G 打断后又出现。
问满足条件的选择方案数,对 998244353 取模。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2)思路解析(DP,类型只有 10 种)
关键等价
“每种类型必须连续一段” 等价于:
在选出的子序列里,某个字母一旦结束(后面出现了别的字母),就不能再出现。
也就是子序列不能出现形如 X ... Y ... X(中间有别的字母 Y)的结构。
DP 状态设计
因为字母只有 A..J 共 10 种,我们用一个 10 位二进制 mask 记录“哪些字母已经出现过”。
再用 last 记录当前子序列最后一个字符是什么(也就是当前正在进行的那一段字母是谁)。
定义:
* dp[mask][last]:处理到当前为止的前若干位置后,能形成的合法选择方案数
其中 mask 表示已经出现过的字母集合,last 表示子序列最后一个字母(0..9 对应 A..J,另外用 10 表示“还没选任何比赛”)。
转移(遍历字符串每一位)
当前字符 c(0..9)时,我们有两种选择:
1. 不选这一场比赛
* 状态不变:dp -> dp
2. 选这一场比赛
* 如果 last == c:说明还在同一段字母里,可以继续选
* 如果 last != c:
* 若 c 没出现过(mask 里没有 c),可以开启新的一段:mask 加上 c,last=c
* 若 c 已出现过,说明想“重新开启已经结束的字母段”,会形成 X...Y...X,非法
答案
所有合法状态的总和里,包含了“一个都不选”的方案(初始状态 mask=0,last=10)。题目要求至少选一场,所以最后要减掉 1。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
3)代码