1838E

· · 题解

开始复健。

$f_{i, j} = (k-1)f_{i-1,j} + f_{i-1,j-1}+[j=n]f_{i-1,j}

这样复杂度可以做到 nm。

我们可以反过来考虑这个问题，合法的减掉不合法的。

总数容易知道是 k^m。

枚举匹配上的长度 i(i=0...n-1)

当匹配上前 i 位的时候，方案数是 \binom{m}{i} ·(k-1)^{m-i}。

答案只需要用合法的减掉不合法的也就是

发现 i 并不大，没必要用什么奇淫技巧，直接算就可以了。 code: [link](https://codeforces.com/contest/1838/submission/209360374)