まず，ある段階で条件に関与しない文字を「自由な文字」と呼ぶこととします．
ここで，
\(dp_{i,j,k} = \) 自由な文字が \(K\) 種中 \(i\) 種である状態で長さ \(j\) の文字列を作るときの通り数とする．( \(k=1\) のとき，ある特定の自由でない文字が自由でない文字の中で最も右にあるときの通り数とする)
とおけば，
\(dp_{i,j,0}=i \times dp_{i,j-1,0}+2 (K-i-1) \times dp_{i+1,j,1}\)
\(dp_{i,j,1}=2 i \times dp_{i,j-1,1}+dp_{i,j-1,0}\)
という遷移式が立ち， \(\Theta(NK)\) で答えを求めることができます．