第二部分的另一构造

设 $h$ 表示最大的 $i$ 满足 $a_i\ge i$。$b_i$ 在数据范围中定义一样，我们考虑将 $i$ 从 $h$ 到 $1$ 考虑。也就是说初始点集为 $\{h+1,\dots,n\}$，我们一个个加入 $i$，并考虑新增的边。

在考虑当前的 $i$ 的时候，若之前已经连接了 $j$ 条边，注意 $i$ 此时向外可以连的边有 $a_i-i-j$ 个“入口”（本来有 $a_i-i$ 个入口，但每条边消耗了一个入口和一个出口）和 $b_i-i-j$ 个出口，如果 $a_i \le b_i$，那么无论出边怎么选择（或者不出边）接下来都恰有一种方案将一条边连到 $i$，让 $i$ 处在一个环中。所以此时我们先决策 $a$，再决策 $b$。注意决策 $b$ 的时候相当于加入了 $i$，所以实际上是 $b_i+1-i-j$ 个出口可以选择。

反之如果 $a_i > b_i$，那么我们对称地先决策 $b$ 后决策 $a$。令 $\hat j = h-i-j$ 即分离出独立变量，按照标算类似的方法做即可。注意这样多项式的总长为 $2h$，但在多点求值的时候会有一个前缀点值直接为 $0$，去掉之后要求值的点应该是 $\le n + 1$ 的。

$\Theta(n\log^2 n) \Rightarrow ?$

与小 Q 的序列不同的是，这里的 $a_i$ 被分成了 $0$ 附近的连续一段和 $y$ 附近的连续一段，那么这个问题看起来就不太一样了，我们想要求对于 $0\le i\le n$：

$$ f_i = \prod_{j=0}^n (c + i + j)^{a_j} \bmod p $$

由于模数 $p=998244353$ 满足 $p-1=7\times 17\times 2^{23}$，离散对数通过 Pohlig-Hellman 算法可以在很高效率内完成分解。因此我们不妨先取对数计算，设原根 $g=3$，

$$ \log_g f_i = \sum_{j=0}^n a_j\log_g (c + i + j) \bmod (p-1) $$

那么我们可以通过一次 $\bmod p-1$ 的卷积完成计算。

总觉得用到离散对数还是显得有点唐突，如果有有效的方法避免离散对数，欢迎指教。