[BZOJ4921]互质序列

题目大意

给定一个序列,求删去一个非空连续子序列后的$gcd$期望值,对998244353取模

分析

首先预处理出前缀和后缀$gcd$,枚举删去的子序列的左端点$l$

令右端点$r$为$l+1$,每次向右移动一个块(即先预处理出$gcd$相等的后缀块),因为最多移动$log_2n$次

时间复杂度为$nlog_2n$