题解 | #环形数组跃迁 #

倍增题目

和上一道题差不多，但还是有很些区别(这道题完全靠自己做出来了！)

题目的意思就是不断的跃迁，然后累加上每一次跃迁到达的位置的值，当然跃迁的次数m最大为1e18;

定义st[i][j]表示从i出发，跃迁了 $2^{j}$ 次后的结果

那么转移的方程：就不是简单的什么st[i][j] = st[st[i][j - 1][j - 1],所以，转移的方程是需要根据题目变化的

容易想到st[i][j] = st[i][j - 1] + 🤔：st[i][j - 1]表示从i跃迁了 $2^{j - 1}$ 后的结果, 那么还需要加上再跃迁 $2^{j - 1}$ 的值。

那肯定不是st[i][j] = st[i][j - 1] + st[i][j - 1]，因为从i跃迁了 $2^{j - 1}$ 后的位置变化了，所以就是跃迁后的位置再跃迁 $2^{j - 1}$

所以 $st[i][j] = st[i][j - 1] + st[跃迁后的位置][j - 1]$

跃迁后的位置怎么求呢？其实就是i跃迁了 $2^{j - 1}$ 次后的位置：

跃迁了 $2^{j - 1}$ 次，每次跃迁的距离是k，所以相乘(特别注意需要对 $2^{j - 1}$ 取模，因为k如果取(n - 1), 那么 $k\times2^{j - 1}$ 会超出long long范围！)

int next_pos = (i + (k * ((1LL << (j - 1)) % n)) % n - 1) % n + 1;

所以转移方程：

for(int j = 1; j < M; j ++){
    for(int i = 1; i <= n; i ++){
        int next_pos = (i + (k * ((1LL << (j - 1)) % n)) % n - 1) % n + 1;
        st[i][j] = st[i][j - 1] + 
    }
}

再此之前需要预处理出所有的st[i][0]:

for(int i = 1; i <= n; i ++){
    int next_pos = (i + k - 1) % n + 1;
    st[i][0] = a[next_pos];
}

最后就是查询环节：
给定初始位置t 和跃迁的次数m

这个就是基本操作了，同样需要更新now_pos

while(q --){
    int t, m; cin >> t >> m;
    int now_pos = t, ans = 0;
    for(int i = M - 1; i >= 0; i --){
        if(m >= (1LL << i)){
            m -= (1LL << i);
            ans = (ans + st[now_pos][i]) % mod;
            now_pos = (now_pos + (k * (1LL << i) % n) % n - 1) % n + 1;
        }
    }
    cout << ans << endl;
}

总代码：

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

#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;


const int N = 1e5 + 10;
const int M = 63;
const int mod = 1e9 + 7;

int n, k, q;
int st[N][M];
signed main(){
    HelloWorld;
    
    cin >> n >> k >> q;
    vector<int> a(n + 10);
    for(int i = 1; i <= n; i ++) cin >> a[i];
    for(int i = 1; i <= n; i ++){
        int next_pos = (i + k - 1) % n + 1;
        st[i][0] = a[next_pos];
    }
    for(int j = 1; j < M; j ++){
        for(int i = 1; i <= n; i ++){
            // int next_pos = (i + (k * (1LL << (j - 1)) % n) % n - 1) % n + 1;
            // int next_pos = (i + (k * ((1LL << (j - 1)) % n)) % n - 1) % n + 1;
            st[i][j] = (st[i][j - 1] + st[next_pos][j - 1]) % mod;
        }
    }
    while(q --){
        int t, m; cin >> t >> m;
        int ans = 0, now_pos = t;
        for(int i = M - 1; i >= 0; i --){
            if(m >= (1LL << i)){
                m -= (1LL << i);
                ans = (ans + st[now_pos][i]) % mod;
                now_pos = (now_pos + (k * ((1LL << i) % n)) % n - 1) % n + 1;
            }
        }
        cout << ans << endl;
    }
    return 0;
}

(注释掉的部分上面会越界报段错误，下面是正确的)