再次膜拜此强题！神级性质之不可能发现系列收藏++；首先，对于长度<=3的情况，我们采取爆搜答案（代码当中是打表）。对于长度>=4的情况，则有如下几条玄妙的性质：
首先我们将 a, b, c 三个字母看做 0, 1, 2。发现（不知道怎么发现的）当我们做出一次变换之后，数列的和在模意义下是不改变的。（*启示：很多关系好像都和取模之后的某些东西有关，例如食物链，此题，and so on）。
那么：当一个序列 T 可以由 S 转化过来时，T必须满足如下几条性质：
1.T的各位字母之和与S的各位字母之和在 %3 的意义下相等。
2.T中必须存在有两个相邻的相同字母（如果不是，不可能是变换后的结果）
当以上两条性质都不满足时，还剩下一种情况，即 S = T。
如何证明是对的？题解如是说：当 n = 4 时，我们可以用打表来验证此性质。当 n > 4 时，我们可以让第一个字母通过变换变成一样的，然后就变成了两个 n - 1 的序列。这样递归下去，当递归到 4 时，即可得证。看起来好像很对的样子，然而怎么证明一定可以把第一个字母变成一样的呢？我并不会……
建立状态 f[i][j][k][p] 表示 dp 到第 i 位，前面的和在模意义下为 j ，最后一位是 k ，是否已经有两个相邻的相同字母的方案数。然后枚举一下，转移就可以惹……
#include <bits/stdc++.h> using namespace std; #define int long long #define maxn 200050 #define mod 998244353 int n, ans, f[maxn][3][3][2], sum; char a[maxn]; int read() { int x = 0, k = 1; char c; c = getchar(); while(c < '0' || c > '9') { if(c == '-') k = -1; } while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * k; } bool Check() { for(int i = 2; i <= n; i ++) if(a[i] != a[i - 1]) return 0; return 1; } bool Check2() { for(int i = 2; i <= n; i ++) if(a[i] == a[i - 1]) return 0; return 1; } void Up(int &x, int y) { x = (x + y) % mod; } void DP(int i, int j, int k, int p) { for(int q = 0; q <= 2; q ++) Up(f[i + 1][q][(q + k) % 3][p | (j == q)], f[i][j][k][p]); } signed main() { scanf("%s", a + 1); n = strlen(a + 1); if(Check()) { puts("1"); return 0; } if(n <= 3) { if(n == 2) puts("2"); else { if(a[1] != a[2] && a[1] != a[3] && a[2] != a[3]) puts("3"); else if(a[1] == a[3]) puts("7"); else puts("6"); } return 0; } for(int i = 1; i <= n; i ++) sum = (sum + a[i] - 'a') % 3; for(int i = 0; i <= 2; i ++) f[1][i][i][0] = 1; for(int i = 1; i <= n - 1; i ++) for(int j = 0; j <= 2; j ++) for(int k = 0; k <= 2; k ++) for(int p = 0; p <= 1; p ++) DP(i, j, k, p); for(int i = 0; i <= 2; i ++) Up(ans, f[n][i][sum][1]); Up(ans, Check2()); printf("%lld ", ans); return 0; }