题解：AT_arc140_f [ARC140F] ABS Permutation (Count ver.)
无名之雾
·
·
题解
来一个重工业垃圾做法。
solution
看一眼题目，限制要求是 |P_i-P_{i+1}=M|，看起来像是要转成一个差为 1 的形式，要不然不太好刻画。但是我转化完之后生成函数推错了。所以考虑一个别的转化。
考虑图论建模。
这等价于在图 G=(V, E) 中（其中 (u, v) \in E \iff |u-v|=M），选取一些边使得它们在排列中相邻。
图 G 是由若干条不相交的路径组成的。
若 N = qM + r，则图 G 包含：
由于对于我们选出的一组连通块，点的访问顺序是有区分的。所以我们要求的实际上是从 G 中的这些链里面选出 k 条边后的带权方案。
如果一个连通块大小大于 1 那么就会有两种顺序。所以如果一个连通块大小大于 1 那么权值就是 2。
于是设 f_n(x) 为长度为 n 的链的生成函数。我们的目标是求出 f_n(x)。
这等价于：用若干段长度为 L_i 的线段覆盖长度为 n 的区间（\sum L_i = n），所有段的权值乘积之和。
考虑 dp。设最后一段的长度为 k。
-
最后一段长度 k=1（即 v_n 是孤立点）。
- 这一段的权值为 1。
- 剩余部分的长度为 n-1，生成函数为 f_{n-1}(x)。
- 贡献项：1 \cdot f_{n-1}(x)。
-
最后一段长度 k \ge 2。
- 这一段的权值为 2x^{k-1}（使用了 k-1 条边，有 2 种方向）。
- 剩余部分的长度为 n-k，生成函数为 f_{n-k}(x)。
- 贡献项：2x^{k-1} \cdot f_{n-k}(x)。
将所有可能的情况求和，得到 f_n(x) 的表达式：
f_n(x) = 1 \cdot f_{n-1}(x) + \sum_{k=2}^{n} 2x^{k-1} f_{n-k}(x)
为了求解这个和式，我们列出 f_n 和 f_{n-1} 的展开式进行错位相减。
f_n = f_{n-1} + 2x f_{n-2} + 2x^2 f_{n-3} + \dots + 2x^{n-1} f_0
f_{n-1} = f_{n-2} + 2x f_{n-3} + \dots + 2x^{n-2} f_0
x f_{n-1} = x f_{n-2} + 2x^2 f_{n-3} + \dots + 2x^{n-1} f_0
做差 f_n - x f_{n-1}：
观察 f_n 和 x f_{n-1} 的后半部分：
相减得：
f_n - x f_{n-1} = f_{n-1} + 2x f_{n-2} - x f_{n-2}
f_n - x f_{n-1} = f_{n-1} + x f_{n-2}
f_n = (1+x) f_{n-1} + x f_{n-2}
因为实际上只需要算出一项，所以直接矩阵快速幂优化一下即可。
对于一条长链，我们有线性递推关系：
\begin{pmatrix} f_{n} \\ f_{n-1} \end{pmatrix} = \begin{pmatrix} 1+x & x \\ 1 & 0 \end{pmatrix} \begin{pmatrix} f_{n-1} \\ f_{n-2} \end{pmatrix}
设转移矩阵 T = \begin{pmatrix} 1+x & x \\ 1 & 0 \end{pmatrix}。
则：
\begin{pmatrix} f_{q+1} \\ f_{q} \end{pmatrix} = T^q \begin{pmatrix} f_{1} \\ f_{0} \end{pmatrix} = T^q \begin{pmatrix} 1 \\ 1 \end{pmatrix}
得到 f_q 和 f_{q+1} 之后就可以求出原来的总生成函数了。
f(x)=f_q^{m-r}\times f_{q+1}^{r}
多项式 \ln,\exp 做一下即可。
于是乎 [x^k]f(x) 就是在整个图中选 k 条边并考虑方向的方案数。
令 g_k=[x^k]f(x)，E_k 表示恰好有 k 条边的排列数，H_k 表示钦定选了 k 条边，剩下 n-k 个连通块任意排列的方案数。
根据排列的性质：
如果我们在图中选了 k 条边，这些边构成了若干连通块。总共有 n-k 个连通块。
这 n-k 个连通块看作整体，在排列中可以任意打乱顺序。
所以：
H_k = g_k \times (n-k)!
二项式反演一下：
E_k = \sum_{j=k}^{n-1} (-1)^{j-k} \binom{j}{k} H_j
这个东西直接拆一下组合数上 NTT 就做完了。
submission。