牛客IOI周赛18-提高组 A
排列
https://ac.nowcoder.com/acm/contest/7225/A
分析
这个可以暴力求出一个循环内的变换。这样可以考虑置换乘法的结合率，然后把置换拆成循环。这样是可以通过的。但是其实现在等同于只有一个操作重复 次，这个其实可以倍增优化，时间复杂度为
。
代码
#include<bits/stdc++.h>
using namespace std;
int read() {
int x = 0,f = 0;char ch = getchar();
while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();}
while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
return f ? -x : x;
}
#define LL long long
const LL N = 1e6+100;
LL n,m,k,B[N],A[N],f[N][40];
int main()
{
n = read();m = read();k = read();
for(int i = 1;i <= n;i++) A[i] = i;
while(m--) {
int l = read(),r = read();
memcpy(B,A,sizeof(B));
for(int i = 1;i <= r-l+1;i++) {
B[r-i+1] = A[l+i-1];
}
memcpy(A,B,sizeof(A));
}
for(int i = 1;i <= n;i++) f[i][0] = A[i];
for(int j = 1;j <= 35;j++) {
for(int i = 1;i <= n;i++) {
f[i][j] = f[f[i][j-1]][j-1];
}
}
for(int i = 1;i <= n;i++) {
int x = i;
for(int j = 35;~j;j--) {
if((k>>j)&1) x = f[x][j];
}
printf("%d ",x);
}
printf("\n");
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int read() {
int x = 0,f = 0;char ch = getchar();
while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();}
while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
return f ? -x : x;
}
const int inf = 0x3f3f3f3f,N = 1e6+100;
int n,m,k,B[N],A[N],pos[N],vis[N],len[N],st[N],top = 0;
int lcm = 1;
int main()
{
n = read();m = read();k = read();
for(int i = 1;i <= n;i++) A[i] = i;
while(m--) {
int l = read(),r = read();
memcpy(B,A,sizeof(B));
for(int i = 1;i <= r-l+1;i++) {
B[r-i+1] = A[l+i-1];
}
memcpy(A,B,sizeof(A));
}
for(int i = 1;i <= n;i++){
int loop = 0;
int t = i;
while(!vis[t]){
loop++;
st[++top] = t;
vis[t] = true;
t = B[t];
}
while(top) len[st[top--]] = loop;
}
for(int i = 1;i <= n;i++) {
int c = k%len[i],pos = i;
while(c--) pos = B[pos];
printf("%d ",pos);
}
return 0;
}
