排列 题解（快速幂的思想）

A 排列

做法，先建模，然后快速幂

m次反转为一次操作，第一次操作后的得到的数组为模式mode。

例如 mode=[3,2,1]，其中mode[1]=3的含义为after[1]=before[3],即变换后数组的第1个位置存放原数组第3个位置的数。

操作之间满足交换率和结合律，可以类比乘法计算，所以两次操作可以看作x*x,k次操作可以看作x^k。
在这种类比下，我们可以重定义乘号的意义，然后应用快速幂的思想。

重定义乘法
x,y是一个数组，代表操作模式，得到乘法定义如下
x*y代表在x的基础上进行y变换，具体做法如下

void cheng(int a[],int b[])//a*=b;
{
    for(int i=1;i<=n;i++)temp[i]=b[i];//防止a和b为同一数组时修改自身。
    for(int i=1;i<=n;i++)a[i]=temp[a[i]];
}

完整代码如下

#include <iostream>
using namespace std;
const int maxn=100005;
int ans[maxn],temp[maxn],mode[maxn];
int n,m,k;
void cheng(int a[],int b[])//a*=b;
{
    for(int i=1;i<=n;i++)temp[i]=b[i];//防止a=b的情况
    for(int i=1;i<=n;i++)a[i]=temp[a[i]];
}
void mypow(){
    int t=k;
    while(t){
        if(t&1)cheng(ans,mode);
        cheng(mode,mode);
        t>>=1;
    }
}
void init(){
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)ans[i]=mode[i]=i;
    int l,r;
    while(m--){
        cin>>l>>r;
        while(l<r){
            swap(mode[l++],mode[r--]);
        }
    }
}
int main(){
    init();
    mypow();
    for(int i=1;i<=n;i++)cout<<ans[i]<<' ';
    return 0;
}