部分点

\(DP[x][y][z][w][state]\) を「 K を \(x\) 個、 Y を \(y\) 個、 O を \(z\) 個、 T を \(w\) 個使い、suffix \(4\) 文字が KYOTO、TOKYO とそれぞれ何文字マッチしているかを \(state\) で表したときの通り数」という形で動的計画法を行うことで、\(O(N^4)\) （定数倍大きめ）で解くことが出来ます。

満点

答えを「TOKYOを含まない個数」-「TOKYO、KYOTOをともに含まない個数」と変形します。

\(2\) つの対象をともに包除原理で数えます。前者は、まずTOKYOを置く個数 \(x\) を決め打ち、disjointになるよう長さ \(5\) の区間 \(x\) 個を置いてから残りの文字を配置することにします。通り数に \((-1)^x\) を掛けて計上したものが求めるものです。

後者について考えます。さっきと異なり禁止パターンであるTOKYO、KYOTOを置いていく際に両者が重なることがあります。このときTOKYOTO...とKYOTOKYO...の \(2\) 種類の区間が生まれますが、長さが \(5\) の倍数となるときに限り \(-1\) の重みが付いています。

ここでTOとKYOに分割して考えると、それぞれ使った個数が分かれば残りの文字の置き方も二項係数の積で書くことができます。よって \(DP[x][y][z]\) を「禁止パターンが \(x\) 個の区間からなり、TOを \(y\) 個、KYOを \(z\) 個使ったときの重みの総和」と定義すれば、全てを \(O(N^3)\) で計算できます。