「GDOI2020模拟赛day2」我的朋友们

默认翻转了$a_i$顺序，下文多项式省略$(x)$

设当前区间为$(i-L,i]$到最终结束的期望步数为$dp_i$

令$A_i=a_ix+1-a_i$

令$P_i=\prod_{j\in(i-L,i]}A_j$

令$F_i=\sum_{j=1}^i dp_jx^j$

令$\displaystyle G_i=F_{i-1}P_i,dp_i=\frac{[x^i]G_i} {coef_i}$

其中常数$coef_i=1-[x^0]P_i=1-\prod_{j\in(i-L,i]}(1-a_j)$，容易预处理得到

用分治$\text{NTT}$，过程中维护

$P_{l,r}=\prod_{j\in(r-L,l]}A_j$

$\displaystyle G_{l,r}=F_{l-1}P_{l,r}$

显然$G_{i,i}=G_i$

分治转移如下：

$\displaystyle G_{l,mid}=G_{l,r}\prod_{j\in (mid-L,min(l,r-L)]} A_j$

$P_{l,mid}=P_{l,r}\prod_{j\in (mid-L,min(l,r-L)]} A_j$

先求出$G_{l,mid}$

$P_{mid+1,r}=P_{l,r}\prod_{j\in (max(r-L,l),mid+1]} A_j$

$\displaystyle G_{mid+1,r}=(G_{l,r}+(F_{mid}-F_{l-1})P_{l,r})\prod_{j\in (max(r-L,l),mid+1]} A_j$

归纳上述过程，发现实际上同步维护的部分只需要维护

$G_{l,r}$的$[l-(r-l),r]$项，$P_{l,r}$的$[0,r-l]$项

只需要实现

通过$G_{l,r}$的$[l-(r-l),r]$项得到$G_{l,mid}$的$[l-(mid-l),mid]$，以及$G_{mid+1,r}$的$[l,r]$

通过$P_{l,r}$的$[0,r-l]$得到$P_{l,mid}$的$[0,mid-l]$，$P_{mid+1,r}$的$[0,r-mid-1]$

初始状态

$P_{L,n}=\prod_{j\in(n-L,L]}A_j$

$G_{L,n}=0$

在分治过程中有非常多的$P_{l,r}$都是空的。。

可以分治$\text{NTT}$预处理出转移系数$\displaystyle \prod_{i=l}^r A_i$，或者用记忆化暴力求出，复杂度为$O(n\log ^2n)$

在转移过程中维护的部分长度与$r-l$同阶，因此复杂度为$O(n\log^2 n)$