排列 题解

模拟出一次操作后的排列，那么一次操作相当于乘上了这样一个置换。找出所有环，则每个数会在环上移动 步，按顺序求出环上的元素，那么加上 后对环长取模即可得到最后的数。

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;

int n,m,k,l[N],r[N];
int p[N],vis[N],ans[N];
int sta[N],top;

int main() {
    n=read(),m=read(),k=read();
    for (int i=1;i<=n;++i) p[i]=i;
    for (int i=1;i<=m;++i) l[i]=read(),r[i]=read(),reverse(p+l[i],p+r[i]+1);
    for (int i=1;i<=n;++i) {
        if (vis[i]) continue;
        top=0; sta[top++]=i;
        for (int j=p[i];j!=i;j=p[j]) vis[j]=1,sta[top++]=j;
        ans[i]=sta[k%top];
        for (int j=p[i],c=1;j!=i;j=p[j],++c) ans[j]=sta[(c+k)%top];
    }
    for (int i=1;i<=n;++i) printf("%d ",ans[i]); puts("");
    return 0;
}