「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)\)