Solution
因为所有数不相同，所以若给所有 $|p_i - p_j| = k$ 的 $i, j$ 连边将得到 $O(n)$ 条链。
$|p_i - p_{i+ 1}| \not = k$ 的关系不好刻画，而相等却可以，所以考虑容斥。
设 $S_e$ 表示满足第 $i$ 条边的题目中的限制的排列的集合。则有
$$|\bigcap\limits_{e \in E} S_e| = \sum\limits_{V \subseteq E} (-1)^{|V|}|\bigcap\limits_{e \in V} \overline{S_e}|$$
考虑套路地对每一个 $|V| = j$ 求一个 $g_j$ 为所有同样大的 $V$ 的贡献之和。于是考虑如何计算 $g_j$。
先考虑如何刻画 $|\bigcap\limits_{e \in V} \overline{S_e}|$，容易得到
$$|\bigcap\limits_{e \in V} \overline{S_e}| = (n - |V|)! \times 2^{\operatorname{cnt}(V)}$$
其中 $cnt(V)$ 表示 $V$ 中连边得到的大小至少为二的连通块个数。
然后可以 DP。先对原序列按 $a_i \bmod k$ 第一关键字，$a_i$ 第二关键字排序，使得所有可能的连边都在相邻两个数之间。记状态为 $dp_{i, j, 0/1}$ 表示考虑了前 $i$ 个数之间的连边有 $j$ 条，最后一个数是否有向前的连边。
