ARC140F()

感谢LJC00118的指导/bx

首先需要容斥,算至少\(K\)对相邻数差为\(M\)的情况。设算出的结果为\(g\),真实答案为\(f\),则\(g_k=\sum\binom{i}{k}f_i\),二项式反演即可得到\(f\)。

将排列相邻差为\(M\)的位置连边,发现这些位置构成若干条链且每一条链上的数单调递增或单调递减。

考虑\(M=1\)的情况。将\(1\sim n\)的序列划分成若干条链,反转一些长度\(\ge 2\)的链然后将其任意排列。可以根据链的数量算出边数(即钦定差为\(M\)关系的数量),容易发现边数为\(k\)的方案的个数与\(g_k\)等价。

写出单链的OGF:

\([x^k]F^i\)表示划分出\(i\)条链,总长度为\(k\)的方案数。可以使用卷积求出\(i=0\sim k\)的每一项。注意特殊考虑\(i=k\)的情况,此时\(j=0\)时\([x^{k-i}](\frac{2}{1-x})^j=1\)。

对于\(M\neq 1\)的情况,发现可以按照模\(M\)的余数将排列中的数分组,每组同\(M=1\)的情况一样,因此将每组的答案卷起来(注意还要考虑每组之间链的顺序),得到\(g\),进而得到\(f\)。

————————

感谢LJC00118的指导/bx

首先需要容斥,算至少\(K\)对相邻数差为\(M\)的情况。设算出的结果为\(g\),真实答案为\(f\),则\(g_k=\sum\binom{i}{k}f_i\),二项式反演即可得到\(f\)。

将排列相邻差为\(M\)的位置连边,发现这些位置构成若干条链且每一条链上的数单调递增或单调递减。

考虑\(M=1\)的情况。将\(1\sim n\)的序列划分成若干条链,反转一些长度\(\ge 2\)的链然后将其任意排列。可以根据链的数量算出边数(即钦定差为\(M\)关系的数量),容易发现边数为\(k\)的方案的个数与\(g_k\)等价。

写出单链的OGF:

\([x^k]F^i\)表示划分出\(i\)条链,总长度为\(k\)的方案数。可以使用卷积求出\(i=0\sim k\)的每一项。注意特殊考虑\(i=k\)的情况,此时\(j=0\)时\([x^{k-i}](\frac{2}{1-x})^j=1\)。

对于\(M\neq 1\)的情况,发现可以按照模\(M\)的余数将排列中的数分组,每组同\(M=1\)的情况一样,因此将每组的答案卷起来(注意还要考虑每组之间链的顺序),得到\(g\),进而得到\(f\)。