令邻接矩阵是 $\mathbf G$，所有元素 $\le k$ 的满足条件的序列的 GF 为 $F_k(z)$。那么如果不考虑 $b_s,s,b_t,t$，答案无非就是 $\mathbf G^{-1} F_k(\mathbf G)$。

不难发现计数 $F_k(z)$ 可以拆出最大值，即 $$ F_k(z) = z\sum\limits_{i=1}^k (1+F_{i-1}(z))^2 $$

那么考虑维护出所有 $F_k(\mathbf G)$，自然就是 $$ F_k(\mathbf G) = \mathbf G\sum\limits_{i=1}^k (1+F_{i-1}(\mathbf G))^2 $$

注意到平方只要计算 $k$ 次，那么计算所有 $F_k(\mathbf G)$ 的总复杂度就是 $O(k^2n^2+kn^3)$。

令 $\mathbf v_s$ 是行向量 $([i=s])_{i=1}^n$。令 $F_{b_s,0,k}(z),F_{0,b_t,k}(z),F_{b_s,b_t,k}(z)$ 分别是限定了序列首尾的 GF，那么有 $$ \begin{aligned} F_{b_s,0,k}(z) &= z \sum\limits_{i=1}^k \left[F_{b_s,0,i-1}(z)(1+F_{i-1}(z))+[i=b_s](1+F_{i-1}(z))\right] \\ F_{0,b_t,k}(z) &= z \sum\limits_{i=1}^k \left[F_{0,b_t,i-1}(z)(1+F_{i-1}(z))+[i=b_t](1+F_{i-1}(z))\right] \\ F_{b_s,b_t,k}(z) &= z \sum\limits_{i=1}^k \left[F_{b_s,0,i-1}(z)F_{0,b_t,i-1}(z)+[i=b_s]F_{0,b_t,i-1}(z)+[i=b_t]F_{b_s,0,i-1}(z)+[i=b_s=b_t]\right] \end{aligned} $$

不妨直接维护出所有 $\mathbf v_s F_{b_s,0,k}(\mathbf G),F_{0,b_t,k}(\mathbf G) \mathbf v_t^T,\mathbf v_s \mathbf G^{-1} F_{b_s,b_t,k}(\mathbf G) \mathbf v_t^T$。根据递推式，维护前两者可以做到 $O(kn^2)$（向量乘矩阵），维护第三者可以做到 $O(kn)$（向量乘向量）。注意到 $\mathbf G$ 可能没有逆，但是只需要注意到递推时必然会多贡献一个 $\mathbf G$，去掉即可。

时间复杂度 $O(k^2n^2+kn^3+qkn^2)$。