容易想到\(O(nm)\)的做法
\(dp_{i,j}\)表示考虑前\(i\)个\(b\)序列，已经匹配了前\(j\)个\(a\)序列的方案数
我们可以贪心的让\(a_i\)能匹配就匹配，换言之如果我们确定了\(a_i\)在\(b_j\)位置匹配上，那我们要保证在\(b_j\)到和\(a_{i-1}\)匹配的位置中不能出现数字\(a_i\)
容易得到递推柿子：
\[dp_{i,j} = dp_{i-1,j-1}+dp_{i-1,j} \times (K-1+[j=n])
\]
其中\(\times (K - 1)\)的原因是保证\(a_i\)每次和最小的位置匹配，\([j=n]\)则因为\(a_{n}\)在匹配后后面的部分可以随便选
我们发现这个做法不太能优化了，正难则反，我们考虑用总的贡献减去不合法的贡献
首先考虑总的情况，显然是\(k^m\)
对于不合法的贡献，我们不妨表示为匹配上了前\(i\)位但未匹配到\(i+1\)位的情况，我们不妨设它出现的方案数为\(f_i\)
则我们可以得到\(f_i = \binom{m}{i}(k-1)^{m-i}\)其中\(\binom{m}{i}\)表示从\(m\)个中选\(i\)个位置，这些位置钦定他们匹配\(a_i\)的前\(i\)位，\(k-1\)的原因是对于序列\(b\)的每个位置\(j\)，如果他没有被钦定，他都要保证不能匹配到下一个被钦定的位置。对于最后若干个位置，因为我们让他不匹配到\(i+1\)，不妨理解成让\(m+1\)位置钦定为填\(a_{i+1}\)，所以前面若干个位置不能填\(a_{i+1}\)，所以也是\(k-1\)种可能
最终复杂度\(O(\log m + n)\)