题解：P14009 「florr IO Round 1」数字游戏

· · 题解

题目大意

给定序列 a，求：

\sum^{n}_{l=1} \sum^{n}_{r=l}\sum^{a_l}_{b_1=1}\sum^{a_{l+1}}_{b_2=1}\sum^{a_{l+2}}_{b_3=1}\dots\sum^{a_{r}}_{b_{r-l+1}=1} [\gcd(b_1,b_2,b_3,\dots,b_{r-l+1})=1]

其中，n 为序列 a 元素的个数。

思路

比较套路。

\begin{aligned} &\ \ \ \ \ \sum^{n}_{l=1} \sum^{n}_{r=l}\sum^{a_l}_{b_1=1}\sum^{a_{l+1}}_{b_2=1}\sum^{a_{l+2}}_{b_3=1}\dots\sum^{a_{r}}_{b_{r-l+1}=1} [\gcd(b_1,b_2,b_3,\dots,b_{r-l+1})=1]\\ &=\sum^{n}_{l=1} \sum^{n}_{r=l}\sum^{a_l}_{b_1=1}\sum^{a_{l+1}}_{b_2=1}\sum^{a_{l+2}}_{b_3=1}\dots\sum^{a_{r}}_{b_{r-l+1}=1} \sum_{k \mid \gcd(b_1,b_2,b_3,\dots b_{r-l+1})}\mu(k)\\ &=\sum_{k=1}^{\max(a_1,a_2,a_3\dots,a_n)}\mu(k)\sum_{l=1}^{n}\sum_{r=l}^{n}\sum^{a_{l+1}}_{b_2=1}\sum^{a_{l+2}}_{b_3=1}\dots\sum^{a_{r}}_{b_{r-l+1}=1}\prod_{i=1}^{r-l+1}[k\mid b_i]\\ &=\sum_{k=1}^{\max(a_1,a_2,a_3\dots,a_n)}\mu(k)\sum_{l=1}^{n}\sum_{r=l}^{n}\prod_{i=l}^{r}\sum_{b_i=1}^{a_i}[k\mid b_i]\\ &=\sum_{k=1}^{\max(a_1,a_2,a_3\dots,a_n)}\mu(k)\sum_{l=1}^{n}\sum_{r=l}^{n}\prod_{i=l}^{r}\lfloor\frac{a_i}{k}\rfloor \end{aligned}

下文设 V=\max(a_1,a_2,\dots,a_n)。

由上面式子，我们得到了一个 O(Vn^2) 的解法。

考虑类似于整除分块做法，\lfloor \frac{a_i}{k}\rfloor 只会改变 \sqrt{V} 次。总共修改 N\sqrt{V} 次。用线段树维护，有 O(n\sqrt{V}\log_2 n) 的做法。

但是线段树的常数非常大，不负众望的炸了。

考虑模仿替罪羊树：设置一个值 K，单次修改的次数大于 K 时暴力重构。此时 K=\lfloor\frac{3.5\times10^4}{3}\rfloor=11666 但是实测 K=5000 更优。

于是就过了本题。