치환 군 과 순환 절
제목 링크
하나의 배열 A (1, 2, 3... n) 는 하나의 교체 p 를 거 쳐 k 번 변환 한 후에 하나의 배열 B 를 얻 을 수 있다.
A 가 한 번 의 변환 을 거 친 후의 결 과 를 구하 다.
생각:
이 문 제 는 군 과 순환 절 을 바 꾸 는 개념 을 알 아야 한다.
순환 절 이 뭐야?예 를 들 면
1 2 3 4 5 위 에서 아래 를 보다
4 1 5 2 3
1 - > 4 - > 2 - > 1 (1, 4, 2) 은 하나의 순환 절 이 고 길 이 는 3 이다. 3 - > 5 - > 3 (3, 5) 은 하나의 순환 절 이 고 길 이 는 2 이다.
교체 횟수 가 순환 절 길이 일 때 는 변화 가 없 는 셈 이다.
순환 절의 길 이 를 r 로 설정 하고 우 리 는 모든 순환 절 을 단독으로 변환 합 니 다.k 회 변환 이 필요 합 니 다. 마지막 으로 한 번 변 경 된 결 과 를 얻어 야 합 니 다.
B 를 z 번 으로 바 꾸 고 B ^ z = A 는 B 를 다시 바 꾸 는 것 입 니 다.그러면 이때 A 가 z * k 번 을 바 꾼 셈 이다.
z*k%r = 0。한 번 변환 해 야 하 는 결 과 는 z1 을 취하 여 z1 * k% r = 1 을 만 드 는 것 입 니 다.
모든 순환 절 을 다 처리 하면 답 을 얻 을 수 있다.
#pragma warning(disable:4996)
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
vector vec;
int n, k;
int a[100005], b[100005], vis[100005];
void calc()
{
int r, i, inv;
ll temp;
r = vec.size();//
for (i = 1; i < r; i++)
{
temp = (ll)i*(ll)k;
if (temp % (ll)r == 1)inv = i;
// k ， inv
}
for (i = 0; i < r; i++)
{
b[vec[i]] = vec[(i + inv) % r];
}
}
int main()
{
int i, j;
scanf("%d%d", &n, &k);
for (i = 1; i <= n; i++)
scanf("%d", &a[i]);
for (i = 1; i <= n; i++)
{
int x = a[i];
vec.clear();// vector
while (!vis[x])//
{
vec.push_back(x);
vis[x] = 1;
x = a[x];
}
calc();//
}
for (i = 1; i <= n; i++)
printf("%d ", b[i]);
printf("
");
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
