逆天。
转化后的题意
\(q\) 组询问，求有 \(n-m\) 个自由元素，\(m\) 个限制元素的错排问题。
\(1\le n, m, q\le 2\times10^5\)
首先写出两种组合意义的转移方程：
\[\begin{aligned} f(n, m) &= f(n,m-1)-f(n-1,m-1)\\ f(n, m) &= (m-1)f(n-1,m-2)+(n-m)f(n-1,m-1) \end{aligned} \]当我们将 \((n,m),(n,m-1),(n-1,m-1),(n-1,m-2)\) 四个位置放到坐标系中，注意到它们排列为一些平行四边形。显然只要知道其中两个就能通过解上面给出的方程得到另外两个。所以我们维护所有 \((f(a, b),f(a+1,b+1))\) 的数对，显然可以在 \(\Theta(1)\) 时间内使得 \(a\) 或 \(b\) 增加 \(1\)，结合回滚莫队即得解。
标签：方程,le,GDKOI2023,元素,aligned,错排 From： https://www.cnblogs.com/kyeecccccc/p/18014184