abc367

D - Pedometer

思路

由于是环形，为了方便处理，先把整个环形区间转化为线性的，a[1...n] -> a[1...n,1...n - 1]，这样的数组长度扩张为$2 * n - 1$。令$sum[ ]$数组是a数组取模以后的前缀和，假如$sum_i = k, sum_j = k$，那么$\sum_{k = i + 1} ^{j}{a_k}$一定是$m$的倍数。然后对于长度为$n$的连续区间维护和当前$a_i \% m$的有几个相同的个数即可。所以我们可以动态的维护长度为$n$的区间中每个数出现的次数，从$l = 1, r = n$开始，一直$l ++, r ++$保证维护区间的长度为$n$，每次维护区间的时候，求$a_i$产生的贡献。

代码

/*
* @Author:  Hfuubigstrength
* @email:   2854614012@qq.com
* @Date:   2024-08-17 20:44:55
*/
#include <bits/stdc++.h>
#define int long long
#define PII pair<int,int>
#define LL long long
#define fi first
#define se second
#define debug(a) cout<<#a<<"="<<a<<endl;
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define sz(x) (int)x.size()
#define r(x, y) rand() % (y - x + 1) + x
using namespace std;

const int N = 400010;
int a[N], n, b[N], m, sum[N], ans;
map<int,int>mp;
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; i ++ ){
        cin >> a[i];
        a[n + i] = a[i];
    } 

    for(int i = 1; i <= 2 * n - 1; i ++ ) a[i] += a[i - 1];
    for(int i = 1; i <= 2 * n - 1; i ++ ) a[i] %= m;
    for(int i = 1; i <= n; i ++ ){
        mp[a[i]] ++;
    }
    for(int i = 1; i <= n; i ++ ){
        ans += mp[a[i]] - 1;
        mp[a[i]] --;
        mp[a[i + n]] ++;

    }
    cout << ans << endl;
    return 0;
}

E - Permute K times

发现$k$是$1e18$级别的，肯定要$\log$算法，应该很容易能想到倍增，令$f[i][j]$代表下表为$i$的数跳$2^j$能跳到的位置$i’$，对于每一个$i$看$k$

的每一位$bit$是不是1，如果是就跳$2^{bit}$步。

/*
* @Author:  Hfuubigstrength
* @email:   2854614012@qq.com
* @Date:   2024-08-18 16:49:11
*/
#include <bits/stdc++.h>
#define int long long
#define PII pair<int,int>
#define LL long long
#define fi first
#define se second
#define debug(a) cout<<#a<<"="<<a<<endl;
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define sz(x) (int)x.size()
#define r(x, y) rand() % (y - x + 1) + x
using namespace std;

const int N = 200010;
int f[N][70], n, k, a[N], to[N];//下标为i的数跳2^j次能到的位置

signed main() {
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> n >> k;
    for (int i = 1; i <= n; i ++ ) cin >> to[i];
    for (int i = 1; i <= n; i ++ ) cin >> a[i];
    for (int i = 1; i <= n; i ++ ) f[i][0] = to[i];
    for (int i = 1; i <= 60; i ++ )
        for (int j = 1; j <= n; j ++ )
            f[j][i] = f[f[j][i - 1]][i - 1];

    for (int i = 1; i <= n; i ++ ) {
        int idx = i;
        for (int j = 0; j <= 60; j ++ ) {
            if (k >> j & 1)
                idx = f[idx][j];
        }
        cout << a[idx] << " ";
    }
    return 0;
}