题解：CF1921F Sum of Progression

lgx57 · 2024-12-07 17:47:44 · 题解

根号分治模板题。

对于这种题目，直接暴力显然是不行的。于是要用到根号分治。

根号分治的基本思路就是设一个阈值 B，然后根据询问的大小分 2 种情况讨论：

d \ge B

这种情况下直接暴力。

if (d>=B){
    int ans=0;
    for (int now=s,i=1;i<=k;now+=d,i++){
        ans+=a[now]*i;
    }
    cout<<ans<<' ';
}

d < B

这种情况下需要预处理。我们设

st_{i,j}=[(j-1) \bmod i]+1

（中括号不是艾弗森括号，只是普通的中括号）。

然后：

sum_{i,j}=a_{st_{i,j}}+2a_{st_{i,j}+i}+ \cdots + \lceil \frac{j}{i} \rceil a_{j}

sum2_{i,j}=a_{st_{i,j}}+a_{st_{i,j}+i}+ \cdots + a_{j}

for (int i=1;i<B;i++){
    for (int j=1;j<=n;j++){
        if (j<=i) sum[i][j]=a[j],sum2[i][j]=a[j];
        else sum[i][j]=sum[i][j-i]+(j+i-1)/i*a[j],sum2[i][j]=sum2[i][j-i]+a[j];
    }
}

于是有：

\sum _{i=1}^{k} ia_{s+(i-1)d}=sum_{d,s+(k-1)d}-sum_{d,s-d}-\lceil \frac{s}{d} \rceil (sum2_{d,s+(k-1)d}-sum2_{d,s-d})

（式子稍微有点长，具体可以看代码）。

else{
    int L=s,R=s+(k-1)*d;
    int ans1=sum[d][R]-sum[d][L-d];
    int cnt=(s+d-1)/d-1;
    int ans2=cnt*(sum2[d][R]-sum2[d][L-d]);
    cout<<ans1-ans2<<' ';
}

那么时间复杂度为 O(Bn+\frac{qn}{B})。这个式子在 B= \sqrt n 时取到最小值，所以这种技巧叫做根号分治。

完整代码