F - Normalization

F - Normalization

操作において、不変の値に気付けると強いの意味が分かった

abcを012とするとmod3上で合計は変化しない
自明に作れないケース以外はうえで作れる
nが3以下の時はどの操作でも真ん中が使われるため例外的に全部は作れない

Submission #4271328 - AtCoder Regular Contest 094

// 連 最 mo
mint dp[k5 * 2][2][3][3];
void solve() {
cin >> s;
setMod(998244353);
int n = sz(s);
if (n <= 5) {
set res;
set t;
res += s;
t += s;
while (sz(t)) {
set u;
fora(ti, t) {
rep(i, n - 1) {
str ns = ti;
if (ns[i] != ns[i + 1])ns[i] = ns[i + 1] = 'a' + 'b' + 'c' - ns[i] - ns[i + 1];
if (res.count(ns) == 0) {
res += ns;
u += ns;
}
}
}
t = u;
}
fin(sz(res));
}
//aaaaa なら 1
bo same = 1;
rep(i, n - 1)if (s[i] != s[i + 1]) same = 0;
if (same)fin(1);

// ren la mo
dp[0][0][0][0] = 1;
dp[0][0][1][1] = 1;
dp[0][0][2][2] = 1;
rep(i, n - 1) {
rep(r, 2) {
rep(l, 3) {
rep(m, 3) {
rep(c, 3) {
dp[i + 1][r || l == c][c][(c + m) % 3] += dp[i][r][l][m];
}
}
}
}
}
//abc のような連続しhないものは初期値でしか作れないため
mint res = 1;
rep(i, n - 1)if (s[i] == s[i + 1]){res--;break;}
int m = 0;
rep(i, n)m += s[i];
rep(i, 3)res += dp[n - 1][1][i][m % 3];
cout << res << endl;
}