【题解】P5151 HKE与他的小朋友

实际上，位置的关系可以看做一组递推式，\(f(a_i)=f(a_j),f(a_j)=f(a_t),etc...\)那么我们可以压进一个矩阵里面。

考虑到这个矩阵是\(O(n^2logn)\)的，我们观察我们单位矩阵的性质，发现每行的轮换的。

那么我们愉快地只记录第一层的信息然后矩阵快速幂了。

但是我现在可以用更贴切的办法描述这道题了！

小朋友们的换位置关系构成了一个群！

由于群的运算满足结合律，那么我们就可以快速幂了～

#include<iostream>

#include<cstring>

#include<queue>

#include<cstdlib>

#include<vector>

#include<set>

#include<map>

#include<cstdio>

#include<cmath>

#include<algorithm>

#include<bitset>

#include<ctime>

using namespace std;

#define TMP template < class ins >

#define endl '\n'

#define RP(t,a,b) for(register int t=(a),edd=(b);t<=edd;t++)

#define ERP(t,a) for(register int t=head[(a)];t;t=e[t].nx)

#define DRP(t,a,b) for(register int t=(a),edd=(b);t>=edd;t--)

typedef long long ll;

const int maxn=100005;

int n,k;

TMP inline ins qr(ins tag){

    char c=getchar();

    ins x=0;

    int q=0;

    while(c<48||c>57)

    q=c==45?-1:q,c=getchar();

    while(c>=48&&c<=57)

    x=x*10+c-48,c=getchar();

    return q==-1?-x:x;

}

struct seat {

    int data[maxn];

    inline int& operator [](int x){

    return data[x];

    }

    inline void unis(){

    RP(t,1,n)

        data[t]=t;

    }

    inline seat operator *(seat x){

    seat ret;

    RP(t,1,n)

        ret[x[t]]=data[t];

    return ret;

    }

    inline seat operator *=(seat x){

    return (*this)=(*this)*x;

    }

    inline seat operator ++(void){

    seat ret=(*this);

    seat ans;

    RP(t,1,n)

        ans[t]=ret[ret[t]];

    return (*this)=ans;

    }

    inline seat operator^(int x){

    int p=x;

    seat ret;

    ret.unis();

    seat base=(*this);

    while(p){

        if(p&1)

        ret*=base;

        ++base;

        p>>=1;

    }

    return ret;

    }

    inline seat operator ^=(int x){

    int p=x;

    return (*this)=(*this)^p;

    }

    inline void scan(){

    RP(t,1,n)

        data[t]=qr(1);

    }

    inline void print(){

    RP(t,1,n)

        cout<<data[t]<<' ';

    cout<<endl;

    }

}orzyyb;

int main(){

    n=qr(1);

    k=qr(1);

    orzyyb.scan();

    orzyyb^=k;

    orzyyb.print();

    return 0;

}

巴特西

【题解】P5151 HKE与他的小朋友

【题解】P5151 HKE与他的小朋友

最新文章

热门文章