延庆精神文明建设的门户网站,海淀区城市建设档案馆网站,泸县城乡住房建设厅网站,泰安新浪乐居房产网https://ac.nowcoder.com/acm/contest/5667/J
题目大意#xff1a;给你一个置换A#xff0c;使得置换P^kA,让你求出置换P。
思路#xff1a;我们根据置换A再置换z次#xff0c;那么就等于置换p 置换z*k次,如果z*k%len0#xff0c;那么将会回到单位序列#xff0c;那我们…https://ac.nowcoder.com/acm/contest/5667/J
题目大意给你一个置换A使得置换P^kA,让你求出置换P。
思路我们根据置换A再置换z次那么就等于置换p 置换z*k次,如果z*k%len0那么将会回到单位序列那我们再置换一次则是置换p即是z*k%len1则z是k在模len下的逆元。我们求出A的每一个循环再求出z就可以求出该循环内的对应位置。因为满足gcdlenk1,那我们可以直接在循环中将i后移z个位置。
#include iostream
#include cstdio
#include fstream
#include algorithm
#include cmath
#include deque
#include vector
#include queue
#include string
#include cstring
#include map
#include stack
#include set
#include cstdlib
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define FILL(a,b) (memset(a,b,sizeof(a)))
#define lson rt1
#define rson rt1|1
#define lowbit(a) ((a)-(a))
#define ios std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
#define fi first
#define sc second
#define scd(a) scanf(%d,a)
#define scdd(a,b) scanf(%d%d,a,b)
#define scddd(a,b,c) scanf(%d%d%d,a,b,c)
#define ac coutans\n
#define pb push_back
#define endl \n
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pairll,ll pii;
int dx[4] {-1,1,0,0},dy[4] {0,0,1,-1};
const ll mod998244353;
const ll N 5e510;
const ll M 250000;
const double eps 1e-4;
//const double piacos(-1);
ll re(){ll x;scanf(%lld,x);return x;
}
ll n,k;
int a[N];
int vis[N];
int b[N];
vectorint g;
void gg(){ll lg.size(),p0;for(ll i0;il;i) if((i*k)%l1) {pi;break;}for(ll i0;il;i) b[g[i]]g[(ip)%l];
}
void slove(){nre(),kre();for(int i1;in;i) a[i]re();for(int i1;in;i){if(vis[i]) continue;int xi;g.clear();while(!vis[x]){vis[x]1;g.pb(x);xa[x];}gg();}for(int i1;in;i) printf(%d ,b[i]);
}
int main(){int t1;// tre();while(t--) slove();return 0;
}
