我们先想一下若干全是 \(-1\) 怎么做
我们可以一层一层的考虑。对于最后一层，我们可以发现 \((\frac{n}{2}, n]\) 这些数每对位置应该恰好有一个，因此我们可以计算出方案数为 \((\frac{n}{2})! \times 2^{\frac{n}{2}}\) ，其中前面指 \((\frac{n}{2}, n]\) 的全排列方案数，后面 \(2^{\frac{n}{2}}\) 则指对于一对位置放在哪一个
然后我们考虑如果不全是 \(-1\) 怎么做
我们可以发现如果有一个数字 \(a_i > \frac{n}{2}\) ，则他的位置是固定的，我们即不用考虑他的全排列，也不用考虑他放在一对中的哪个位置；但是这还没完，如果有个数字\(a_i \leq \frac{n}{2}\) ，则他虽然不会影响到排列的方案书，但对于他所在的对中，另一个数的位置是确认的
因此不妨设当前这层中\(a_i > \frac{n}{2}\) 的数有 \(num_1\) 个， \(a_i \leq \frac{n}{2}\) 的数有 \(num_0\) 个，则我们可以得到这一层的方案数为 \((\frac{n}{2}-num_1)! \times 2^{\frac{n}{2}-num_0-num_1}\)
因此我们只需要预处理出在某一范围内的数字有多少个即可，最终复杂度\(O(n+k)\)