23752 - 카드 잘 섞기

step 1

2번 쿼리는 그냥 하면 됩니다.

1번 쿼리에서 카드 장수가 홀수인 경우만 생각해 봅시다. 카드 5장이 다음과 같이 있습니다. 카드의 위치는 위에서 부터, 0-base로 셉니다.

카드의 인덱스를 2배 한 다음 절반씩 나누고 잘 끼워 넣습니다.

그럼 카드의 장수를 $N$이라 할 때 각 카드의 처음 인덱스를 $a_i$라 할 때 셔플 후의 인덱스는 $(a_i*2)\%N$이 됩니다. 이 동작을 $z$번 반복하면 $a_i*2^z\%N$이 됩니다.

step 2

카드의 장수가 짝수인 경우입니다. 제일 아래쪽 카드의 위치는 절대 바뀌지 않습니다.

마지막 카드만 빼고 살펴봅시다. 5장일 때와 다르지 않습니다.

즉 $1\,x\,y\,z((y-x)\%2==1)$ 쿼리는 $1\,x\,y-1\,z$과 완벽히 같습니다.

코드

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
using namespace std;
long long int mul(long long int x, long long int y, long long int z) {
	long long int t = 1, cnt = 0, count = 0, i;
	cnt = (x / 1000000) * y % z;
	cnt *= 1000000;
	cnt %= z;
	cnt += x % 1000000 * y % z;
	return cnt % z;;
}
long long int pow(long long int p, long long int r) {
	long long int t = 2, tt = 1;
	while (p != 0) {
		if (p % 2 == 1) {
			tt = mul(tt, t, r);
			tt %= r;
		}
		p /= 2;
		t = mul(t, t, r);
		t %= r;
	}
	return tt;
}
int main() {
	long long int n, m, i, s = 1, j, t, p;
	scanf("%lld%lld%lld", &n, &m, &p);
	for (i = 1; i <= m; i++) {
		long long int x, y, z, w;
		scanf("%lld", &x);
		if (x == 1) {
			scanf("%lld%lld%lld", &y, &z, &w);
			if ((z - y) % 2 == 1) z--;
			if (p<y || p>z) continue;
			t = pow(w, z - y + 1);
			p = y + mul(p - y, t, z - y + 1);
		}
		else {
			scanf("%lld", &y);
			p -= y;
			if (p <= 0) p += n;
		}
	}
	printf("%lld", p);
	return 0;
}