一道很显然是 \(dp\) 的题
我们设 \(f_{i,j}\) 表示钦定了前 \(i\) 个数，其中 \([i-j+1,i]\) 这些数中没有重复(就是说有成为 \(1\sim K\) 的排列的可能性)时的成本之和
我们可以用刷表法来表示这个 \(dp\) 的转移方法：
\[\begin{cases}
f_{i+1,j+1} \leftarrow f_{i,j} \times (K - j) & (j < K - 1) \\
f_{i+1,j+1} \leftarrow f_{i,j} + 1 & (j = K - 1) \\
f_{i+1,1} \leftarrow f_{i,j} \times K & (j = K) \\
f_{i+1,k} \leftarrow f_{i,j} & (j \neq K,k \in [1,j])
\end{cases}
\]
其中第一行表示这些数还没构成一个排列，我们想让他构成一个排列，从 \((K-j)\) 个数中选一个；第二行表示马上就要构成一个排列了，我们要把贡献加上去；第三行表示我们已经构成了一个排列，下一列可以从 \(K\) 个数中随便填；第四行表示我们填了 \([i-j+1,i]\) 这些数中已经出现了的一个，使得我们把这个常为 \(j\) 的可能成为排列的值破坏成了常为 \(k\) 的值
要是你认为这么做就算完了，那你就太天真了！(一转攻势
我们看第二个式子，他的贡献显然不是 \(+1\) 这么简单，而应该是加上前 \(i\) 个数中， \([i-j+1,i]\) 这些数没有重复的方案数才对，因此第二个式子计算贡献是不对的
我们考虑再设一个 \(g_{i,j}\) 表示前 \(i\) 个数中， \([i-j+1,i]\) 这些数没有重复的方案数
我们改一下第二个式子：\(f_{i+1,j+1} \leftarrow f_{i,j} + g_{i+1,K}\)，完美解决
但还不完美，对于第四个式子的计算，我们要花费 \(O(K)\) 的时间，总复杂度变成了 \(O(nK^2)\) ，不足以通过此题
这个简单，显然的差分优化 \(dp\) ，最终复杂度 \(O(nK)\)