2020牛客暑期多校训练营(第二场)Just Shuffle
程序员文章站
2022-05-12 12:28:43
...
题目
这道题在打的时候没做出来(废话)
然后补题时看了一点paper
再看了别人的标程
过了
代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m,i,j,k,l,o,p,a[100005],v[100005],ans[100005],x,y,t;
void egcd(ll x,ll y,ll &a,ll &b)
{
if(!y)
{
a=1;
b=0;
return;
}
egcd(y,x%y,b,a);
b-=a*(x/y);
}
int main()
{
scanf("%lld%lld",&n,&m);
for (i=1;i<=n;i++)scanf("%lld",a+i);
for (i=1;i<=n;i++)
{
if(v[i]) continue;
v[i]=1;
vector<ll> vi;
vi.push_back(i);
for (j=a[i];!v[j];j=a[j]) vi.push_back(j),v[j]=1;
t=m%vi.size();
egcd(t,vi.size(),x,y);
if (x<0) x+=vi.size();
for (j=0;j<vi.size();j++) ans[vi[j]]=vi[(j+x)%vi.size()];
}
for (i=1;i<=n;i++) printf("%lld ",ans[i]);
cout<<endl;
}
推荐阅读
-
2019牛客暑期多校训练营(第二场)H Second Large Rectangle
-
2020牛客暑期多校训练营(第四场)——Basic Gcd Problem
-
2020牛客暑期多校训练营(第五场)
-
2020牛客暑期多校训练营(第九场) The Flee Plan of Groundhog
-
2020牛客暑期多校训练营Groundhog and Apple Tree(树形dp,贪心)
-
2020暑期牛客多校训练营第九场(K)The Flee Plan of Groundhog(lca,树形dp)
-
2020牛客多校第三场-J Just Shuffle
-
2020牛客暑期多校训练营(第二场)Cover the Tree
-
2020牛客暑期多校训练营(第一场)H-Minimum-cost Flow
-
2020牛客暑期多校 第一场 F Infinite String Comparision(字符串)