F - Find 810s

以下のようなdpを考えます。

• $dp[i][j]=i$ 番目まで決めて810810...810 のうち $j$ 文字目まで出てくる通り数

毎回 $M+1$ 通り遷移先を求めていると $O(MNK)$ になってTLEしてしまいます。
遷移先が制約下では $j,j+1,j+2,j+3$ の $4$ 通りしかありえないことと、$j$ が $mod\ 3$ で等しいなら $j,j+1,j+2,j+3$ へ遷移する個数の分布も等しいことを利用します。
予め $mod \ 3$ が $0,1,2$ の場合のそれぞれについてこの分布を計算しておくことで、遷移が $O(1)$ で出来るようになり、計算量が $O(M+NK)$ になって間に合います。