ARC094 F : Normalization(700)
作成日：2018.09.04
最終更新日：2018.09.04
問題概要
文字$a,b,c$からなる文字列$S$に対し操作「隣接する文字で互いに異なるものを1組選び、それらの文字を$a,b,c$のうちいずれとも異なる文字に置き換える」を$0$回以上繰り返して作ることのできる文字列の個数を$998244353$で割った余りを求めよ。
制約
$2 \leq |S| \leq 2 \times 10^5$
考え方
まず、操作を1回以上行うことによって作れる文字列を考える。
操作から明らかであるが、同じ文字が並んでいる箇所がない文字列は作れない。
また不変量について考えるために$a,b,c$をそれぞれ$0,1,2$とすると、操作によって文字に対応する数の総和の$mod \: 3$が変わらないことが分かる。
これ以上条件がないように見えるが、これらが十分条件であることも示せない。
そこで、$|S|$が小さい場合において全探索をすることによりこれを確かめる。
長さ$n$の文字列においてすべての解を全探索で求める計算量は$O((3^n)^2 n)$(以下のソースコードのsolve関数はmapを使っているので、さらに$n$がかかる)であるから、$n \leq 5$くらいまでを確かめることにする。
すると$n=3$の時は十分条件になっていないが、他ではそうなっていることが分かる。
先に挙げた2つの条件が十分条件にもなっている$n$において作れる文字列のうち、$a,b,c$それぞれが先頭であるものをすべて含んでいれば、先頭1文字を作った後に残りの部分を作れることから$|S| \gt n$の時もそれらの条件が十分条件になっていることが分かる。
以上より$n = 3$の時は全探索をし、それ以外の時は2つの条件を満たしている文字列の数を計算すれば良い。
但し全探索により気づくように、$S$をなす文字がすべて同じである時の答えは$1$であり、$S$中に同じ文字が並んでいる箇所がなければ答えは$1$大きくなる。
条件を満たす文字列の数を直接求めるのは大変なので、条件を満たさない文字列を数えることにする。
すなわち、$mod \: 3$が等しい文字列のうち同じ文字が並んでいる箇所がない文字列を数える。
これは先頭から文字を決めていき、$mod \: 3$の値と直前の文字を状態として持つDPをすれば$O(|S|)$で求められる。
このDPで求めた値を$3^{|S|-1}$から引いた値が答えとなる。
ソースコード
マクロ等はこちら
const LL mod = 998244353;
string S;
LL dp[200010][3][3];
int solve(){
set<string> ans{S};
queue<string> Q; Q.push(S);
while(!Q.empty()){
string x = Q.front(); Q.pop();
repp(i,1,S.size()) if(x[i-1] != x[i]){
string y = x;
if(x[i-1] != 'a' && x[i] != 'a') y[i-1] = y[i] = 'a';
else if(x[i-1] != 'b' && x[i] != 'b') y[i-1] = y[i] = 'b';
else if(x[i-1] != 'c' && x[i] != 'c') y[i-1] = y[i] = 'c';
if(ans.find(y) == ans.end()){
Q.push(y);
ans.insert(y);
}
}
}
return ans.size();
}
int main(){
cin >> S;
int n = S.size();
if(n == 3) return cout << solve() << endl , 0;
int d = 0 , m = S[0] - 'a';
repp(i,1,n){
if(S[i-1] != S[i]) ++d;
m += S[i] - 'a';
}
if(d == 0) return cout << 1 << endl , 0;
dp[1][0][0] = dp[1][1][1] = dp[1][2][2] = 1;
repp(i,1,n) repp(j,0,3) repp(k,0,3) repp(l,0,3) if(k != l)
(dp[i+1][(j+l)%3][l] += dp[i][j][k]) %= mod;
LL ans = 1 , ans2 = 0 , t = 1;
repp(i,1,n) (ans *= 3) %= mod;
repp(k,0,3) (ans2 += dp[n][m%3][k]) %= mod;
cout << (ans - ans2 + mod + (d==n-1?1:0)) % mod << endl;
return 0;
}解法まとめ
$|S| = 3$の時は全探索で求める。(5-22,27行)
そうでなく$S$がすべて同じ文字からなる時の答えは$1$である。(30,33行)
それ以外の場合は、先頭から文字を決めていき$a,b,c$をそれぞれ$0,1,2$とみなした時の文字に対応する数の総和の$mod \: 3$と直前の文字を状態に持つDPを行い、$S$と文字に対応する数の総和の$mod \: 3$が同じである3つの状態の値それぞれを$3^{|S|-1}$から引いた値が答えである。
但し、$S$中に同じ文字が並んでいる箇所がなければさらに$1$を加えたものが答えである。(34-40行)