给定字符串 (S),每次操作选择两个不同的相邻字符,将其变成不同的另外一个(如 ab
(
ightarrow)cc
)
求经过这种操作能变成的字符串数量(mod 998244353)。
(2le |S|le 2cdot 10^5,Sigma={ exttt{a,b,c}})。
对于字符串 (T),找一些 (S) 能变成 (T) 的充要条件。首先 (S=T) 不言而喻,只考虑 (S e T) 的情况。
- (T) 必须有两个连续字符相同。
- 令
abc
的权值分别为 (0,1,2),则权值之和 ( ext{sum}(S)mod 3) 不变。
事实证明这个东西在大部分情况下都是必要的,除了 (|S|= ext{sum}(S)=3) 也就是第一个样例的情况,直接特判跑路即可。
回到原问题,先特判掉 (S) 全相等和 abc
的排列的情况。
设 (k= ext{sum}(S)),求有多少个 (T) 使得 ( ext{sum}(T)equiv kpmod 3),且 (T) 中有两个连续字符相同。
反面考虑,变成求有多少个 (T) 满足 ( ext{sum}(T)equiv kpmod 3),且 (T) 中任意两个连续字符都不同。
当 (3 mid n) 时根据对称性,答案显然为 (2^{n-1}),当 (3|n) 时麻烦一点,算一算 ((x+x^2)^{2n/3}mod(x^3-1)) 就可以得到答案为:
[3^{n-1}-2^{n-1}+[3|n](1-3[3|k])2^{n/3-1}+[forall iin[1,n),S_i
e S_{i+1}]
]
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 200003, mod = 998244353;
int n, k, ans; char S[N]; bool flg1, flg2;
int ksm(int a, int b){
int res = 1;
for(;b;b >>= 1, a = (LL)a * a % mod)
if(b & 1) res = (LL)res * a % mod;
return res;
} void qmo(int &x){x += x >> 31 & mod;}
int main(){
scanf("%s", S); n = strlen(S);
for(int i = 0;i < n;++ i) k += S[i] - 'a';
for(int i = 0;i < n-1;++ i)
if(S[i] == S[i+1]) flg1 = true; else flg2 = true;
if(!flg2) return puts("1"), 0;
if(n == 3 && k == 3) return puts("3"), 0;
qmo(ans = !flg1 + ksm(3, n-1) - ksm(2, n-1));
if(!(n % 3)){
if(k % 3) qmo(ans += ksm(2, n / 3 - 1) - mod);
else qmo(ans -= ksm(2, n / 3));
} printf("%d
", ans);
}