题解 | #环形数组跃迁#

由于步长固定，不难想到用倍增。

$nxt_{bit, i}$ 记录从 $i$ 走 $2^{bit}$ 步走到了哪里， $sum_{bit, i}$ 记录从 $i$ 走 $2^{bit}$ 步的总和。

则有 $nxt_{bit, i} = nxt{bit-1, nxt_{bit-1, i}}$ （走两次）, $sum_{bit, i} = sum_{bit-1, i} + sum_{bit-1, nxt_{bit-1, i}}$ 。

时间复杂度 $O(nlog_m +q log_m)$ 。

void solve(){
    ll n = read(), k = read(), q = read();
    vector<ll> a(n+1);
    vector<vector<ll>> nxt(61, vector<ll>(n+1)), sum(61, vector<ll>(n+1));
    for(ll i=1;i<=n;i++) a[i] = read();
    for(ll i=1;i<=n;i++){
        nxt[0][i] = (i-1+k)%n+1;
        sum[0][i] = a[(i-1+k)%n+1];
    }
    for(ll i=1;i<=60;i++){
        for(ll j=1;j<=n;j++){
            nxt[i][j] = nxt[i-1][nxt[i-1][j]];
            sum[i][j] = (sum[i-1][j] + sum[i-1][nxt[i-1][j]])%MOD;
        }
    }
    while(q--){
        ll t = read(), m = read();
        ll ans = 0;
        for(ll bit=60;bit>=0;bit--){
            if(m >> bit & 1){
                ans = (ans +sum[bit][t])%MOD;
                t = nxt[bit][t];
            }
        }
        print(ans);
    }
}

c++火车头

// FZANOTFOUND
#include <bits/stdc++.h>
using namespace std;

#define pb push_back 
#define eb emplace_back 
#define fi first
#define se second
#define ne " -> "
#define sep "======"
#define fastio ios::sync_with_stdio(false);cin.tie(0);
#define all(a) a.begin(), a.end()

typedef long long ll;
typedef unsigned long long ull;
typedef long double db;
typedef pair<long long,long long> PLL;
typedef tuple<ll,ll,ll> TLLL;
const ll INF = (ll)2e18+9;
const ll MOD = 1000000007;
//const ll MOD = 998244353;
const db PI = 3.14159265358979323;

//io functions
inline void rd(ll &x){x=0;short f=1;char c=getchar();while((c<'0'||c>'9')&&c!='-') c=getchar();if(c=='-') f=-1,c=getchar();while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();x*=f;}  
inline ll read(){ll x=0;short f=1;char c=getchar();while((c<'0'||c>'9')&&c!='-') c=getchar();if(c=='-') f=-1,c=getchar();while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();x*=f;return x;}  
inline void pt(ll x){if(x<0) putchar('-'),x=-x;if(x>9) pt(x/10);putchar(x%10+'0');}
inline void print(ll x){pt(x), puts("");}
inline void print(PLL x){pt(x.fi), putchar(' '), pt(x.se), putchar('\n');}
inline void print(vector<ll> &vec){for(const auto t:vec)pt(t),putchar(' ');puts("");}
inline void print(const map<ll, ll>& g) {for(const auto& [key, value]:g){cout<<"key: "<<key<<ne<<value<<" ";}puts("");}
inline void print(vector<PLL> &vec){puts(sep);for(const auto v:vec){print(v);}puts(sep);}
inline void print(const map<ll, vector<ll>>& g) {for (const auto& [key, value] : g) { cout << "key: " << key << ne;for (const auto& v : value) {cout << v << " ";}cout << endl;}}

//fast pow
ll ksm(ll a, ll b=MOD-2, ll M=MOD){a%=M;ll res=1;while(b){if(b&1){res=(res*a)%M;}a=(a*a)%M;b>>=1;}return res;}

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());//rng()
ull randint(ull l, ull r){uniform_int_distribution<unsigned long long> dist(l, r);return dist(rng);}


void init(){

}

void solve(){

}

int main(){
    init();
    ll t = 1;
    //t = read();
    while(t--){
        solve();
    }
}