对于 $n\lt m$ 的情况,显然无解。下文认为 $n\ge m$。
我们先选 $m$ 个位置固定,方案数为 $\binom{n}{m}$。剩下 $(n-m)$ 个位置,显然这一部分就是错排列问题:
求长为 $n$ 的排列 $p$ 中,对 $\forall i$ 都有 $p_i\neq i$ 的方案数。
不好直接算,考虑容斥。答案就是全部方案数减去至少在一个位置有 $p_i=i$ 的方案数。
后一部分还得容斥(因为会算重)。所以错排列问题的答案就是如下式子:
$$\sum_{i=0}^n (-1)^i\binom{n}{i}(n-i)!$$
把 $\binom{n}{i}$ 展开,尝试化简:
$$\sum_{i=0}^n (-1)^i\frac{n!}{i!(n-i)!}(n-i)!$$
高兴地把 $(n-i)!$ 约掉,把与 $i$ 无关的 $n!$ 提到外面去:
$$n\times\sum_{i=0}^n (-1)^i\times\frac{1}{i!}$$
后面的式子直接在预处理 $n!$ 及其逆元时跑前缀和就可以了。
所以最终的答案就是:
$$\binom{n}{m}\times (n-m)!\times \sum_{i=0}^{n-m}(-1)^i\times\frac{1}{i!}$$
时间复杂度 $O(n_{\max}+T)$。
注意负数取模。