题解：P14461 【MX-S10-T2】『FeOI-4』青年晚报

挺有趣的一个组合数题。

发现这个 $F$ 函数和 $G$ 函数结合的形式十分丑陋，所以第一件事应该是把 $F$ 和 $G$ 拆开。

设 $F_{i,j}$ 表示 $F_i$ 第 $j$ 项系数，有关系式 $F'_{i,j}=(j+1)\times F_{i,j+1}$。

可以发现 $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)$ 的复杂度。