Just Shuffle

10825 단어

제목.


전송문

분석하다.


이 문제는 그룹을 바꾸는 지식을 사용했기 때문에 구체적인 결론은 거물 논문을 참고할 수 있다.선행 결론이 나왔을 때, 다시 유클리드를 확장해서 곱셈 역원을 구하면 ok

코드

#include

#define ll long long

using namespace std;

const int MAXN=1e5+100;
vector<ll> vec;

ll exgcd(ll a,ll b,ll &x,ll &y)//           
{
	if(b==0)
	{
		x=1;y=0;return a;
	}
	ll c=exgcd(b,a%b,y,x);
	y-=a/b*x;
	return c;
}

ll l,k,t[MAXN],ans[MAXN];
bool v[MAXN];

int main()
{
	scanf("%lld%lld",&l,&k);
	for(int i=1;i<=l;i++) scanf("%lld",&t[i]);
	for(int i=1;i<=l;i++)
	{
		if(v[i]) continue;
		v[i]=1;vec.clear();vec.push_back(i);
		for(int j=t[i];j!=i;j=t[j]) vec.push_back(j),v[j]=1;
		if(vec.size()==1)
		{
			ans[i]=t[i];continue;
		}
		ll inv,y;
		exgcd(k%vec.size(),vec.size(),inv,y);
		if(inv<0)  inv+=vec.size();
		for(int j=0;j<vec.size();j++) ans[vec[j]]=vec[(j+inv)%vec.size()];
	}
	for(int i=1;i<=l;i++) printf("%lld ",ans[i]);
}

----오리지널 문장, 참고만
입사 UI 화면 em 떨림
thank-you-stars로 Go의 라이브러리에 스타 보내기

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage