![AT2062 [AGC005D] ~K Perm Counting 题解](/uploads/reation/bcimg10.png)
AT2062 [AGC005D] ~K Perm Counting 题解
AT2062 [AGC005D] ~K Perm CountingAT2062 [AGC005D] ~K Perm Counting一个有趣的做法。发现合法的情况直接算是不好算的，我们考虑进行二项式反演，也就是钦定有多少个是不合法的。考虑一个位置 iii 可以向 i±ki\pm ki±k 连边。我们不妨考虑左边是排列，右边是位置的二分图。那么本质上钦定 iii 个不合法的就是对于这样的二分图满足其匹配是 i−1i - 1i−1。对于匹配是 iii，长度是 jjj 的链，方案数就是 (i+
