题解：P14461 【MX-S10-T2】『FeOI-4』青年晚报
Binah_cyc
·
·
题解
挺有趣的一个组合数题。
发现这个 F 函数和 G 函数结合的形式十分丑陋，所以第一件事应该是把 F 和 G 拆开。
设 F_{i,j} 表示 F_i 第 j 项系数，有关系式 F'_{i,j}=(j+1)\times F_{i,j+1}。
\begin{aligned}
&F_{i,j}\\
=&G_{i-1,j}+G'_{i-1,j}\\
=&G_{i-1,j}+(j+1)\times G_{i-1,j+1}\\
=&F_{i-2,j}-F'_{i-2,j}+(j+1)\times(F_{i-2,j+1}-F'_{i-2,j+1})\\
=&F_{i-2,j}-(j+1)\times F_{i-2,j+1}+(j+1)\times F_{i-2,j+1}-(j+1)\times (j+2) \times F_{i-2,j+2}\\
=&F_{i-2,j}-(j+1)\times (j+2) \times F_{i-2,j+2}\\
&G_{i,j}\\
=&F_{i-1,j}-F'_{i-1,j}\\
=&F_{i-1,j}-(j+1)\times F_{i-1,j+1}\\
=&G_{i-2,j}+G'_{i-2,j}-(j+1)\times(G_{i-2,j+1}
+G'_{i-2,j+1})\\
=&G_{i-2,j}+(j+1)\times G_{i-2,j+1}-(j+1)\times G_{i-2,j+1}-(j+1)\times (j+2) \times G_{i-2,j+2}\\
=&G_{i-2,j}-(j+1)\times (j+2) \times G_{i-2,j+2}
\end{aligned}
可以发现 F 与 G 的递推式是相同的，所以可以用同一份代码计算 F 与 G。
直接照着这个使用矩阵加速能做到 O(m^3\log n) 的复杂度。
考虑正解，发现转移的第一维步长是偶数，所以如果 n 是奇数则可以先令 n\leftarrow n-1 再特殊处理最后一步。接下来讨论 n 是偶数时的方案。我们将 F 数组的转移示意图画出来。
图中红色边的权值是 1，绿色边的权值是 -(j+1)(j+2)。
我们发现一个 f_{0,j} 对 f_{n,j} 的贡献可以被拆成两部分，一部分是绿色边的边权，另一部分是转移方案数。显然从一个 x 转移到 y 时，绿色边的边权是固定的，即 (-1)^{{x-y}\over 2}\displaystyle \prod _{t=y+1}^{x}t，转移方案数是简单组合数，考虑从 x 走到 y 的时候走了几步绿边，方案数是 \displaystyle \binom{\lfloor{{n}\over {2}}\rfloor}{{x-y}\over 2}。
综上 F_{n,i}=\displaystyle \sum_{j=1}^{\lfloor{{m-i}\over 2}\rfloor}(-1)^j\prod _{t=i+1}^{i+j\times 2}t \times\binom{\lfloor{{n}\over {2}}\rfloor}{j}\times F_{0,i+j\times 2}，照着这个式子写能做到 O(m^2) 的复杂度。