首先可以考虑容斥，也就是 \(ans=\sum_{i=0}^n (-1)^i\times h_i\times (n-i)!\) ，\(h_i\) 表示有 \(i\) 步限制不满足的方案数。
考虑到如果对于一个排列，连 \(i\rightarrow p_i\) 的边会形成若干个环组成的有向图。那么对于两个相同大小的排列，连接 \(p_i\rightarrow q_i\) 的边同样也会形成若干个有向环。 并且可以发现这样转换可以使题目转换成一个限制对应有向图的一条边，如果一个限制不满足就选择这条边所连接的两个点中的一个，两条边不能选择同一个节点。然后再对此进行计数会方便很多。
由于对于一个固定长度的有向环的方案数是固定的，所以可以设 \(f[i][j]\) 表示对于一个长度为 \(i\) 的环，选择其中 \(j\) 条边不满足限制，并固定好这 \(j\) 条边选择的节点的方案数。但是可以注意到由于环具有对称性，很难通过 \(f[i][j]\) 自身进行转移，所以可以考虑先将环破成链，然后再对链计数即可。所以设 \(g[i][j]\) 表示对于一个长度为 \(i\) 的链，选择 \(j\) 条边并固定好节点的方案数。
每次选出的边组成的子链中包含链左端点的子链长度为 \(k\) ,因为一个长度为 \(k\) 的链有 \(k\) 种固定点的方案，所以有 \(g[i][j]=\sum_{k=0}^{j+1}\space k\times g[i-k][j-k+1]\) 。
由此也可以推出 \(f[i][j]=\sum_{k=0}^{j} \space (k+1)^2\times f[max\)\(\{\)\(0,i-k-2\)\(\}\)\(][j-k]\) 也就是包含 \(1\) 号节点的子链长度为 \(k\) ,这样的子链有 \(k+1\) 种，然后对于任何一种子链都有 \(k+1\) 种固定点的方案。\(f[i][j]\) 和 \(g[i][j]\) 暴力转移是 \(O(n^3)\) 的，其中 \(f[i][j]\) 可以使用前缀和优化做到 \(O(n^2)\) , 而统计答案需要使用的 \(g[i][j]\) 的 \(i\) 满足 \(\sum i=n\) , 所以可以将 \(dp\) 转移部分做到 \(O(n^2)\) , 然后在使用 \(g[i][j]\) 更新 \(h_i\) 。