A, B, C の個数がすべて \(S\) と同じ文字列 \(T\) に対し，\(S\) から \(T\) を得るために必要な操作回数の最小値がいくつになるかを考えます．

\(S\) で文字 \(x\) だったが \(T\) で文字 \(y\) になっている場所の個数を \(C[x][y]\) と置くことにします．

操作回数の最小値は \(C[x][y]\) のみで定まります． 具体的には次のように計算できます．

• まず，\(x\neq y\) に対し \(C[x][y]>0, C[y][x]>0\) なら，文字 \(x,y\) を入れ替える \(1\) 回の操作で \(C[x][y],C[y][x]\) の値をそれぞれ \(1\) 減らせる．そして，このような操作を可能な限り行って損することはない．

• 上の操作が行えなくなったときは，\(C[\)A\(][\)B\(]=C[\)B\(][\)C\(]=C[\)C\(][\)A\(]\) となっている．この値を\(X\) と置く．また，\(C[\)A\(][\)C\(]=C[\)C\(][\)B\(]=C[\)B\(][\)A\(]\) となっている．この値を\(Y\) と置く． ここで，\(X,Y\) の少なくとも一方は \(0\) である． \(X>0\) なら，ABC \(\to\) BAC \(\to\) BCA という \(2\) 回の操作で \(X\) を \(1\) 減らすことができる．そして，このような操作を可能な限り行って損することはない．\(Y\) についても同様で，\(2\) 回の操作で \(1\) 減らすのが最適である．

このような操作の結果，\(K\) 回以内の操作でできる文字列 \(T\) を数え上げればよいです． \(C[x][y]\) をすべて決定してしまえば，あとは二項計数の計算で対応する \(T\) の個数がわかります．

\(C[x][y]\) を決定することは，上の最適手順で行う操作回数を決め打つことと同値です．

\(1\) 種類目の操作における \((x,y)=(\)A,B\(),(\)A,C\(),(\)B,C\()\) の操作回数，及び \(2\) 種類目の操作における \(X\) (または \(Y\)) の値，という \(4\) つの自由度があるので，これを全て試してみます．

すると考えるべき操作は \(O(K^4)\) 通りなので，計算量的に間に合います．

よってこの問題は全体で \(O(N+K^4)\) 時間で解けます．

解答例