T17:Chain Contestant

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）代码

#include <bits/stdc++.h>
using namespace std;

const long long MOD=998244353;                              // 题目要求取模

int main(){                                                 // 主函数入口
    ios::sync_with_stdio(false);                            // 加速输入输出
    cin.tie(nullptr);                                       // 加速输入输出

    int N;                                                  // 比赛场数
    string S;                                               // 比赛类型字符串
    cin>>N;                                                 // 读入 N
    cin>>S;                                                 // 读入 S

    static long long dp[1<<10][11];                         // dp[mask][last]，last=0..9表示A..J，10表示未开始
    static long long ndp[1<<10][11];                        // 下一步转移用的数组

    dp[0][10]=1;                                            // 初始：什么都没选，方案数为1

    for(int idx=0;idx<N;idx++){                             // 遍历每一场比赛
        int c=S[idx]-'A';                                   // 把字符转成 0..9

        for(int mask=0;mask<(1<<10);mask++){                // 清空 ndp
            for(int last=0;last<=10;last++){                // 清空 ndp
                ndp[mask][last]=0;                          // 置0
            }
        }

        for(int mask=0;mask<(1<<10);mask++){                // 枚举出现过的字母集合
            for(int last=0;last<=10;last++){                // 枚举当前最后一个字母
                long long cur=dp[mask][last];               // 取当前方案数
                if(cur==0)continue;                         // 为0则跳过

                ndp[mask][last]=(ndp[mask][last]+cur)%MOD;  // 情况1：不选当前比赛，状态不变

                if(last==c){                                // 情况2a：选当前比赛且和 last 相同，继续同一段
                    ndp[mask][last]=(ndp[mask][last]+cur)%MOD; // 加到同状态
                }else{                                      // 情况2b：选当前比赛且和 last 不同
                    if((mask&(1<<c))==0){                   // 只有当 c 之前没出现过，才允许开启新段
                        int nmask=mask|(1<<c);              // 把 c 加入已出现集合
                        ndp[nmask][c]=(ndp[nmask][c]+cur)%MOD; // 转移到 last=c 的新状态
                    }                                       // 若 c 已出现过则非法，不转移
                }
            }
        }

        for(int mask=0;mask<(1<<10);mask++){                // 把 ndp 复制回 dp
            for(int last=0;last<=10;last++){                // 把 ndp 复制回 dp
                dp[mask][last]=ndp[mask][last];             // 更新 dp
            }
        }
    }

    long long ans=0;                                        // 统计答案
    for(int mask=0;mask<(1<<10);mask++){                    // 枚举所有mask
        for(int last=0;last<=10;last++){                    // 枚举所有last
            ans=(ans+dp[mask][last])%MOD;                   // 累加所有合法方案
        }
    }

    ans=(ans-1+MOD)%MOD;                                    // 去掉“一个都不选”的方案（题目要求至少选一场）
    cout<<ans<<endl;                                        // 输出答案
    return 0;                                               // 结束
}