题解

思路

先选出恰好 $m$ 个不动点，再让其余 $k=n-m$ 个位置形成错排。因此答案为

若 $m>n$，答案为 $0$。错排数满足 $D(0)=1,D(1)=0$，以及

做法

读入全部询问并取得最大 $n$，预处理阶乘、逆阶乘和错排数。每组用阶乘与逆阶乘 $O(1)$ 求组合数。小规模可枚举排列或使用子集放置 DP，中档可逐询问线性计算。

复杂度

预处理和回答总时间复杂度 $O(\max n+T)$，空间复杂度 $O(\max n+T)$。模乘使用 64 位整数。