![【题解】[AGC005D] ~K Perm Counting](/uploads/reation/bcimg2.png)
【题解】[AGC005D] ~K Perm Counting
题意如果一个排列 PPP 满足对于所有的 iii 都有 ∣Pi−i∣≠k|P_i-i|\neq k∣Pi−i∣=k ，则称排列 PPP 是合法的。求有多少种合法的排列。Solution:本题的限制条件很像错排，但是区别在于并不是一一对应的。考虑容斥。问题转化成了求满足其中 KKK 个条件的排列数。考虑这样一个序列：1 1+k 1+2k ... 1+mk 。在二分图中是这样的：考虑其中一条链。为了使结构统一，我们把原始排列拆分成 2n2n2n 个点，这样做的好处是将题意限制转化成了 不能选
