原题链接

题解

关键要素：两次后缀和预处理\(d < \sqrt{n}\)的情况，当\(d\)大于\(\sqrt{n}\)时，直接暴力，总时间复杂度为\(O(n\sqrt{n})\)
代码比讲述要清晰，请直接看代码

code

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a[100005]={0};
ll sufs1[100335][330]={0};//由于i+step，左边要留出足够大的空间
ll sufs2[100335][330]={0};
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin>>t;
    while(t--)
    {
        ll n,q;
        cin>>n>>q;
        ll maxd=sqrt(n);
        for(ll i=1;i<=n+maxd;i++)
            for(ll j=1;j<=maxd;j++)sufs1[i][j]=sufs2[i][j]=0;
        for(ll i=1;i<=n;i++)cin>>a[i];

        for(ll i=n;i>=1;i--)
            for(int step=1;step<=maxd;step++)
                {
                    sufs1[i][step]=sufs1[i+step][step]+a[i];//为什么要i+step，因为当前节点可能是某个step的头节点
                    sufs2[i][step]=sufs2[i+step][step]+sufs1[i][step];
                }

        while(q--)
        {
            ll start,step,num;
            cin>>start>>step>>num;
            if(step<maxd)
                cout<<sufs2[start][step]-sufs2[start+num*step][step]-num*sufs1[start+num*step][step]<<" ";//利用后缀和
            else
            {
                ll ans=0;
                for(int i=0;i<num;i++)
                    ans+=a[start+i*step]*(i+1);
                cout<<ans<<" ";
            }
        }
        cout<<endl;
    }
    return 0;
}