闲话

感觉我现在得先提升自己的 specify 水平（

这题我少说用了七八张草稿纸（只算写了主要过程的
好题！

loj：Light Novel OJ

不要越级做题。
—— 大师 APJifengc

炄勺，砒

小孩召开法

对于长为 \(n\) 的一个排列 \(\{a_i\}\) 的一个子序列 \(a_{i_1},a_{i_2},\dots a_{i_k}\)，如果这个子序列满足 \(a_{i_1}>a_{i_2}<a_{i_3}\dots >a_{i_k}\)，那么这个子序列被称作交替子序列。你要求的就是计数最长的交替子序列等于 \(k\) 的长为 \(n\) 的排列。答案对 \(998244353\) 取模。

\(n\le 10^{18}, \ k\le \min(10^6, n)\)。

~~提示：题目并不难。~~
提示：千万不要在这道题上浪费时间。快跑！

下面会在不产生歧义的情况下简记生成函数，例如记 \(F(x, y)\) 为 \(F\)。

我们设 \(f(n,k)\) 为答案。枚举最大值出现的位置 \(i\)，并枚举左侧交替序列长度为 \(2r(+1)\)，右边为 \(s\)，拼起来可以得到转移方程

\[f(n, k) = \sum_{i \ge 1}\binom{n - 1}{i - 1} \sum_{2r + s = k - 1} \left(f(i - 1, 2r) + f(i - 1, 2r + 1)\right)\times f(n - i, s)
\]

不妨采用 BGF 来刻画这个转移。第一维的占位元是 egf 的，第二维的占位元是 ogf 的，我们构造

\[F(x, t) = \sum_{n\ge 0}\sum_{k\ge 0} f(n, k) \frac{x^n}{n!} t^k
\]

刻画转移需要分别构造第二维 \(k\) 仅取奇/偶数的 BGF，也就是

\[F_0(x, t) = \sum_{n\ge 0}\sum_{k\ge 0} f(n, 2k) \frac{x^n}{n!} t^{2k} = \frac{1}{2} \left(F(x, t) + F(x, -t)\right)
\]

\[F_1(x, t) = \sum_{n\ge 0}\sum_{k\ge 0} f(n, 2k+1) \frac{x^n}{n!} t^{2k+1} = \frac{1}{2} \left(F(x, t) - F(x, -t)\right)
\]

这样可以对照系数，描述转移为

\[\frac{\partial F}{\partial x} = \left(tF_0 + F_1\right) F
\]

我们仍然需要将 \(F(x, t)\) 用只含 \(F(x, t)\) 的式子表示，这就需要我们找到 \(F(x, t)\) 和 \(F(x, -t)\) 之间的关系。
我们可以从 \(F_0, F_1\) 下手。不难想到

\[F_0^2 - F_1^2 = F(x, t)F(x, -t)
\]

因此不妨观察 \(F_0^2 - F_1^2\) 的性质。可以发现

\[\frac{\partial}{\partial x}\left(F_0^2 - F_1^2 \right) = F'(x, t) F(x, -t) - F'(x, -t) F(x, t) = 0
\]

因此我们只需要考察常数项。根据定义，只有 \(F_0\) 在 \(x^0\) 项有 \(1\)，因此

\[F_0^2 - F_1^2 = 1
\]

这就告诉我们 \(F(x, t)\) 和 \(F(x, -t)\) 是一对逆元。因而我们可以用 \(F\) 展开 \(\partial F / \partial x\)，得到

\[\frac{\partial F(x, t)}{\partial x} = F(x, t)\left( \frac{t + 1}{2}F(x, t) + \frac{t - 1}{2} F(x, -t) \right) = \frac{1}{2} \left((t + 1)F^2(x, t) + t - 1\right)
\]

为了化简，我们不妨将 \(\partial x\) 移到等号另一侧，后面只需要两边做偏积分即可。可以得到

\[\frac{\partial F}{(t + 1)F^2 + t - 1} = \frac{\partial x}{2}
\]

看下面的形式，我们不妨先求 \(G = \dfrac{F}{1 - t}\)，最后第二维作差分即得。带入 \(F = G(1 - t)\) 可以得到

\[\frac{\partial G}{(1-t^2)G^2 - 1} = \frac{\partial x}{2}
\]

看下面的形式，我们不妨对左式作部分分式分解，两边乘 \(\alpha = \sqrt{1 - t^2}\) 可以得到

\[\partial(\alpha G) \left(\frac{1}{\alpha G - 1} - \frac{1}{\alpha G + 1} \right) = \alpha \partial x
\]

这时可以偏积分了。众所周知不定积分题不加常数 \(C\) 是要扣分的。因此考虑现在关于 \(x\) 的常数为 \(C_0(t)\) 和 \(C(t) = \exp C_0(t)\)，我们可以得到

\[\begin{aligned} \ln \frac{\alpha G - 1}{\alpha G + 1} &= \alpha x + C_0\\ \frac{\alpha G - 1}{\alpha G + 1} &= Ce^{\alpha x} \end{aligned}
\]

这就能导出 \(G\) 的形式，即

\[G = \frac{1 + Ce^{\alpha x}}{\alpha \left(1 - Ce^{\alpha x}\right)} = \frac{1}{\alpha} \left( \frac{2}{1 - Ce^{\alpha x}} - 1 \right)
\]

这里 \(C(t)\) 的形式也能随之确定。由于 \(G(0, t) = \dfrac{1}{1 - t}\)，有

\[C(t) = \frac{\frac{\alpha}{1 - t} - 1}{\frac{\alpha}{1 - t} + 1} = \frac{1 - \alpha}{t}
\]

这样就能带入了。由于 \([x^0]G\) 不重要，可以删掉它得到新的 \(G\)。这样得到

\[G(x, t) = \frac{1}{\alpha} \left( \frac{2}{1 - \frac{1 - \alpha}{t} e^{\alpha x}} \right) = \frac{2}{\alpha}\left(1 -\frac{1 - \alpha}{t} e^{\alpha x}\right)^{-1}
\]

这个形式就简便了不少。化简一下得到

\[\begin{aligned}

& \frac{2}{\alpha}\left(1 -\frac{1 - \alpha}{t} e^{\alpha x}\right)^{-1}
\\ =\ & \frac{2}{\alpha} \sum_{k\ge 0} \left(\frac{1 - \alpha}{t} e^{\alpha x}\right)^{k}
\\ =\ & \frac{2}{\alpha} \sum_{k\ge 0} t^{-k} (1 - \alpha)^k e^{\alpha k x}
\\ =\ & \frac{2}{\alpha} \sum_{k\ge 0} t^{-k} (1 - \alpha)^k \sum_{i\ge 0} \frac{(\alpha k x)^i}{i!}
\\ =\ & 2 \sum_{k\ge 0} \sum_{i\ge 0} t^{-k} \frac{(k x)^i}{i!} (1 - \alpha)^k \alpha^{i - 1}

\end{aligned}\]

然后现在的主要问题是后面的 \((1 - \alpha)^k \alpha^{i - 1}\)，解决了它的系数提取就可以解决大半问题了。考虑把 \(\alpha\) 展开后观察。

\[(1 - \sqrt{1 - t^2})^k (1 - t^2)^{(i - 1) / 2}
\]

你觉得眼熟吗？我觉得有点眼熟。考虑配凑二叉树方程 \(H(x) = \dfrac{1 - 2x - \sqrt{1 - 4x}}{2x}\) 的形式，首先作换元 \(4x = t^2\)，我们能整理原式为

\[\begin{aligned}

& (1 - \sqrt{1 - 4x})^k (1 - 4x)^{(i - 1) / 2}
\\ = \ & (2x(1 + H))^k (1 - 2x - 2xH)^{i - 1}
\\ = \ & 2^k x^k (1 + H)^k (1 - 2x(1 + H))^{i - 1}

\end{aligned}\]

考虑二叉树方程的递归定义形式 \(H = x(1 + H)^2\)，带入可以得到

\[\begin{aligned}

& 2^k x^k (1 + H)^k (1 - 2x(1 + H))^{i - 1}
\\ = \ & 2^k \left(\frac{H}{(1 + H)^2}\right)^k (1 + H)^k \left(1 - \frac{2H}{1 + H}\right)^{i - 1}
\\ = \ & 2^k H^k (1 + H)^{-k}\left(\frac{1-H}{1 + H}\right)^{i - 1}
\\ = \ & 2^k H^k (1 - H)^{i - 1} (1 + H)^{-k - i + 1}

\end{aligned}\]

我们选用二叉树方程的一个原因是容易求出它的复合逆，即

\[H^{\langle -1\rangle}(x) = \frac{x}{(1 + x)^2}
\]

这样我们便可以使用拉格朗日反演简化系数提取。由于外层函数 \(x^k(1 - x)^{i - 1}(1 + x)^{- k - i + 1}\) 的导数不易求，可以应用另类拉格朗日反演，得到

\[\begin{aligned}

& [x^n]H^k (1 - H)^{i - 1} (1 + H)^{-k - i + 1}
\\ = \ & [x^n] x^k(1 - x)^{i - 1}(1 + x)^{- k - i + 1} \frac{1 - x}{(1 + x)^3} (1 + x)^{2n + 2}
\\ = \ & [x^{n - k}] (1 - x)^{i}(1 + x)^{2n - k - i}
\\ = \ & \sum_{j\ge 0} (-1)^j \binom{i}{j} \binom{2n - k - i}{n - k - j}

\end{aligned}\]

这样我们可以直接用这个系数构造我们需要的生成函数，占位元是 \(x = \dfrac{t^2}{4}\)。代回原式得到

\[2 \sum_{k\ge 0} \sum_{i\ge 0} t^{-k} \frac{(k x)^i}{i!} \sum_{l} \left( \sum_{j\ge 0} (-1)^j \binom{i}{j} \binom{2l - k - i}{l - k - j} \right) \left(\frac{t^2}{4}\right)^l
\]

不妨简化一下组合数的形式，换元 \(l = k + u\)，能得到

\[\begin{aligned}

& 2 \sum_{k\ge 0} \sum_{i\ge 0} t^{-k} 2^k \frac{(k x)^i}{i!} \sum_{u} \left( \sum_{j\ge 0} (-1)^j \binom{i}{j} \binom{k + 2u - i}{u - j} \right) \left(\frac{t^2}{4}\right)^{k + u}
\\ = \ & \sum_{k\ge 0} \sum_{i\ge 0} \sum_{u} t^{k+2u} 2^{1-k-2u} \frac{(k x)^i}{i!}\sum_{j\ge 0} (-1)^j \binom{i}{j} \binom{k + 2u - i}{u - j}

\end{aligned}\]

这个形式就很好提取系数了。可以直接写出 \(G(x, t)\) 的系数

\[g(n, k) = 2^{1 - k} \sum_{2i + r\le k, \ k - r\bmod 2 = 0} r^n (-1)^i \binom{n}{i}\binom{k - n}{\frac{k - r}{2} - i}
\]

可以枚举 \(r\)，这样 \(i\) 的取值范围是连续的一段。这样我们要计算的答案形如

\[f(t) = \sum_{i\ge 0} (-1)^i \binom{n}{i}\binom{k - n}{t - i}
\]

\(f\) 的生成函数 \(F\) 是好写出的，就是

\[F(x) = (1 + x)^{k - n}(1 - x)^n
\]

可以求导后比较系数得到 \(f\) 的递推式，即

\[tf(t) = (k - 2n) f(t - 1) + (t - k - 2) f(t - 2)
\]

发现 \(r\) 的指数相同，可以直接线性筛，这样可以在 \(O(k\log_k n)\) 的复杂度内得到答案。

~~？咋写了那么长~~

Submission.