题解：CF1921F Sum of Progression

根号分治模板题。

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

根号分治的基本思路就是设一个阈值

B

，然后根据询问的大小分

2

种情况讨论：

$d \ge B$

这种情况下直接暴力。

CPP

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}

CPP

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})

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

CPP

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

时取到最小值，所以这种技巧叫做根号分治。

完整代码

题解：CF1921F Sum of Progression

文章操作

相关推荐

评论

题解：CF1921F Sum of Progression