题目链接
题目大意
题目大意
给定一个只由 a、b、c 组成的字符串 S。
要求统计 S 的所有非空子序列中，满足相邻字符不相同的子序列数量，并对 998244353 取模。
注意：即使两个子序列对应的字符串相同，只要选取的位置不同，也算作不同的子序列。
解题思路
解题思路
本题要求统计字符串 S 的所有非空子序列中，满足相邻字符不相同的子序列数量。
由于字符串只包含 a、b、c 三种字符，因此可以按照子序列的结尾字符来设计状态。
1. 状态设计
设：
dp[i][0]：前 i 个字符中，以 a 结尾的合法非空子序列数量dp[i][1]：前 i 个字符中，以 b 结尾的合法非空子序列数量dp[i][2]：前 i 个字符中，以 c 结尾的合法非空子序列数量其中，合法子序列指的是相邻两个字符不相同。
把字符映射成编号：
a -> 0b -> 1c -> 2假设当前处理到第 i 个字符，它对应的编号为 u。
2. 状态转移
对于不是当前字符的结尾状态，也就是 j != u，当前字符不能让这些状态产生新的结尾，因此直接继承上一轮结果：
dp[i][j] = dp[i - 1][j] (j != u)对于当前字符 u，需要考虑两种情况。
第一种情况是不选择当前字符。
那么前面已经存在的、以 u 结尾的合法子序列仍然保留：
dp[i - 1][u]第二种情况是选择当前字符作为新的结尾。
由于题目要求相邻字符不能相同，所以当前字符 u 不能接在以 u 结尾的子序列后面，只能接在以其他字符结尾的合法子序列后面：
sum(dp[i - 1][v]) (v != u)此外，当前字符还可以单独构成一个长度为 1 的子序列：
1所以有：
dp[i][u] = dp[i - 1][u] + sum(dp[i - 1][v]) + 1 (v != u)由于字符只有三种，所以这个式子也可以写成：
dp[i][u] = dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2] + 1这里要注意，虽然式子中包含 dp[i - 1][u]，但它表示的是“不选择当前字符时，保留之前以 u 结尾的子序列”，并不是把当前字符接到这些子序列后面。
3. 为什么可以省略第一维
从状态转移可以发现，计算第 i 轮状态时，只会用到第 i - 1 轮的三个状态：
dp[i - 1][0]dp[i - 1][1]dp[i - 1][2]不会用到更早的状态。
因此，二维数组：
dp[i][3]可以优化成一维数组：
dp[3]其中：
dp[0] 表示当前已经处理过的字符中，以 a 结尾的合法非空子序列数量dp[1] 表示当前已经处理过的字符中，以 b 结尾的合法非空子序列数量dp[2] 表示当前已经处理过的字符中，以 c 结尾的合法非空子序列数量遍历到当前字符 u 时，只需要更新：
dp[u] = dp[0] + dp[1] + dp[2] + 1;其他两个状态不变，相当于自动完成了：
dp[i][j] = dp[i - 1][j] (j != u)因此程序中可以省略第一维，实现滚动数组优化。
4. 最终答案
处理完整个字符串后，所有合法非空子序列一定分别以 a、b、c 中的某一个字符结尾。
所以答案为：
ans = dp[0] + dp[1] + dp[2]由于答案可能很大，需要对 998244353 取模。
5. 复杂度分析
字符串只需要遍历一遍，每个字符的转移都是常数时间。
时间复杂度：
O(n)空间复杂度：
O(1)代码实现
#include <bits/stdc++.h>using namespace std;typedef long long ll;const ll mod=998244353;const int N=3e5+10;ll dp[3];//dp[N][3]:前i个字符, 以a, b, c为结尾的子序列个数有多少string s;int main(){ cin>>s; for(char c:s){ int u; if(c=='a') u=0; if(c=='b') u=1; if(c=='c') u=2; dp[u]=(dp[0]+dp[1]+dp[2]+1+mod)%mod; //不等于u的, 保留上一轮的结果 //u=a时, dp[i][a]=dp[i-1][a](不能选)+dp[i-1][b]+dp[i-1][c](可以选)+1(单独字符) //类似于01背包, 第一维可省略 } ll res=0; for(int i=0;i<3;i++) res=(res+dp[i]+mod)%mod; printf("%lld\n", res); return 0;}