闲话

看很多人在学习龚体
我的评价是
为啥不做小孩召开法？

再论某搞笑题

比赛刚结束就被爆标了（
我不知道是我太弱还是巨佬们太强（
反正我太弱是肯定的

\(\text{Sol 1}：O(k\log^2 k + k\log k \log n)\) by Sol1

~~Sol 1 by Sol1~~

我们容易表出 \(F(1, n)\)——这是广义斐波那契数列的形式，记 \(F(1, n) = Ax^n + By^n\) 的形式，这里可以扩域处理根式，因为可能二次剩余不存在；复杂度不会增加。

随后我们按经典的方式，枚举每一种造成贡献的路径。我们枚举一个长度为 \(k\) 的序列 \(\langle a\rangle\)，其中每个元素 \(a_i \in [0, n]\)，表示这路径在第 \(i\) 层走了 \(a_i\) 步；恒有 \(\sum a_i = n\)。

把所有转移的贡献都一次乘入，我们可以写出

\[F(k, n) = \sum_{a} \left(Ax^{a_1} + By^{a_1}\right) \times \prod_{i = 2}^k t_i^{a_i} \prod_{j = 1}^{i - 1} s^{a_j}
\]

观察 \(s\) 的上标里每个 \(a_i\) 的贡献，我们发现 \(a_i\) 会出现 \(k - i\) 次，因此提出去 \(s^{(k - 1)a_1}\) 就有

\[F(k, n) = \sum_{a} \left(Ax^{a_1} + By^{a_1}\right) s^{(k - 1)a_1} \times \prod_{i = 2}^k t_i^{a_i} s^{(k - i)a_i}
\]

稍微整理一下就可以得到

\[F(k, n) = \sum_{a} \left(A\left(s^{k - 1}x\right)^{a_1} + B\left(s^{k - 1}y\right)^{a_1}\right) \times \prod_{i = 2}^k t_i^{a_i} s^{(k - i)a_i}
\]

也就是说我们要求的值形如

\[\sum_{a} (s^{k - 1}x)^{a_1} \prod_{i = 2}^k \left(t_is^{k - i}\right)^{a_i}
\]

这个形式可以直接构造生成函数，要求的就是

\[[z^n]\left( \frac{1}{1 - \left(s^{k - 1}x\right) z } \times \prod_{i = 2}^k \frac{1}{1 - \left(t_is^{k - 1}\right) z } \right)
\]

这个可以朴素分治乘法+线性递推做到 \(O(k\log^2 k + k\log k \log n)\)。

Sol1 的做法就到这。NaCly_Fish 通过一个我之前想过但是感觉没用的结构推导出了和这个式子同等的结构，并得到了更优的做法。

\(\text{Sol 2}：o(k\log^2 k + k\log k \log n)\) by NaCly_Fish

我们容易对第二维求和得到一个生成函数

\[F_k(x) = \frac{F_{k - 1}(sx)}{1 - t_kx}
\]

边界是（没分解成 \(Ax^n + By^n\) 的形式）

\[F_1(x) = \frac{st_0 + (st_1 - st_0 a) x}{1 - ax - bx^2}
\]

我当时的推导到这就结束了（

可以将 \(F_k(x)\) 展开得到

\[F_k(x) = \frac{st_0 + (st_1 - st_0 a) \left(s^{k - 1}x\right)}{1 - a\left(s^{k - 1}x\right) - b\left(s^{k - 1}x\right)^2} \prod_{i = 2}^k \frac{1}{1 - t_i s^{k - i}x}
\]

这便得到了和上面同等的形式。直接做就行，挺好写的；线性递推甚至可以 \(O(k^2)\)。鰰的实现在这里。~~可以看到复杂度薄纱标程~~

“EI 讲过，这种形式可以做分式分解。“

我出这题的时候还比较小，没学这种科技（
现在倒是学了，可以看这里。

分子本质上是 \(O(1)\) 次求系数操作，不对复杂度作影响，只需要考虑处理分母。我们首先将分母做因式分解，这里可能需要扩域。我们记分母 \(Q(x)\) 被分解为

\[\frac{1}{Q(x)} = \prod_{i = 1}^m \frac{1}{(1 - q_i x)^{d_i}}
\]

这里可能有重根，需要记一个 \(d_i\)，上界是 \(m\) 而不是 \(k + 1\)。

如果我们可以把他改写成

\[Q(x) = \sum_{i = 1}^m \frac{P_i(x)}{(1 - q_ix)^{d_i}}
\]

的形式，就可以轻松提取系数了，最终无非是一系列二项式系数加加乘乘的形式。

对每个 \(i\)，由于这是通分的形式，我们可以知道

\[\frac{P_i(x)}{(1 - q_ix)^{d_i}} Q(x) \equiv 1 \pmod{(1 - q_ix)^{d_i}}
\]

这样我们只需要求出每个 \(\dfrac{Q(x)}{(1 - q_ix)^{d_i}} \pmod{(1 - q_ix)^{d_i}}\) 后求出它在 \(\text{mod }(1 - q_ix)^{d_i}\) 意义下的逆元。

第一步看不懂。鰰说 \(F(x)\equiv (F(x)\text{ mod } A(x)B(x))\text{ mod }A(x)\)，所以我们可以直接分治做。
第二步看不懂。鰰说作换元 \(z = 1 - q_i x\) 后要求的就是模 \(z^{d_i}\) 的逆了。我们可以首先不管这个截断，以 \(z\) 为自变量的式子显然可以直接线性递推。然后加上截断了我们就需要在等号右侧加一个 \((az + b)z^{d_i - 1}\) 来平衡。这个 \(a,b\) 可以通过递推加截断的部分得到？然后把 \(z\) 代换掉就可以直接做了？没看懂。这个手法在鰰的这篇题解里有。

关于为啥要开到负数……为了加个 corner case？