不用代码，思路就行（知道是倍增，不知道怎么写）
给个提示：
这题时间复杂度是2s，也就是2e9
剩下自己想
这是我以前写过的代码，TLE
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod=1e9+7;
int n,k,a[1000005];
ll m,sum[1000005],cnt[1000005],ans;
int main(){
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
int t=i%(k+1);
cnt[t]++;
sum[t]+=a[i];
}
scanf("%lld",&m);
int last=1;
while(m){
int t=last%(k+1);
if(cnt[t]>m){
while(m){
ans=(ans+a[last])%mod;
last=(last+k)%n;
m--;
}
break;
}
last=(last+cnt[t]*(k+1))%n;
ans=(ans+sum[t])%mod;
m-=cnt[t];
}
printf("%lld",ans);
return 0;
}
改为倍增
怎么倍增？我会写ST表不会写倍增（虽然ST表是基于倍增思想的）
那我也不能给你代码啊，思路：用倍增来回寻找ans
你用i进行遍历，每次用num算上数值，保存进b数组中，b[kk]表示第kk步时得数值。每次i=(i+k+1)%n。直到i==0，也就是回到原点，算一个整段
最后，计算答案，答案=（num*整段的个数）+b[剩下的步数]（记得取模）
此时无代码胜有代码
语文课文《京剧趣谈》
《代码趣谈》
A了吗？
把遍历i改成倍增就行了吗?
感觉有个地方没懂，就是倍增的一个单位是多少，是走到原点的步数还是就是一步？
就是说，开始遍历一个回合（从起点再走回起点）
然后再遍历2、4、8…个回合，最后加上多余的？
嗯，代码到时候发出来
好的，稍等
A了吗？
b 数组是不是也会爆 int？
都开long long