blutics   5년 전

도저히 모르겠네요.

어떤 알고리즘으로 푸는 건지 알려주세요 ㅠ

fft로 푸는건가요??

fft 아닌거 같은데.....ㅠ

game2k   5년 전

방금 풀었는데, 저는
{A, B, C} 에서 A ^ (B + C + B^C)를 빠르게 구할 수 없을까? 결합법칙은 성립하지 않는것 같은데?
를 고민해 봤어요

game2k   5년 전

그래서 괄호안의 각 자릿수에 1인 숫자는 몇개인지를 카운트? 비슷하게 하고 XOR을 한꺼번에 해버리는 방식으로 했습니다.

game2k   5년 전

결합이 아니라 분배 ㅠㅠ

blutics   5년 전

좀 더 자세히 설명해주실수 있으신가요 ㅠ

그리고 이게 O(n^2)에 풀리는거 같은데 아닌가요??

game2k   5년 전

지금 밖에 나와서요ㅠ 들어가면 작성해보겠습니다. 복잡도는 O(nlog10억) 인것같네요. n^2 이면 10만제곱인데 안되지 않을까요?

blutics   5년 전

감사합니다~~~ㅠㅠ

cheetose   5년 전

비트단위로 하나하나 쪼개서 계산해나가면 됩니다.

game2k   5년 전

늦어서 죄송합니다 ㅠㅠ 위에 답변 달때 문제를 착각했었네요. 아래는 제가 고민한 방법입니다.

처음에 (A, B, C)에 대해서 생각해보았습니다. 모든 연속하는 부분수열은 다음과 같이 만들 수 있습니다.

(A) ... ⓐ

(A, B), (B) ... ⓑ

(A,B,C), (B,C), (C) ... ⓒ

(A,B,C, D), (B,C,D), (C,D), (D) -> 만약 D도 있다면..

...

수열의 길이가 더 길어져도 위 규칙에 맞게 하면 모든 부분수열을 만들 수 있습니다.

처음에 ⓐ의 부분수열을 ①이라고 하겠습니다. (A 하나만 있음)

다음으로 ⓑ의 부분수열을 고려하면 ①^B + B = A^B + B 를 계산하면 됩니다. 이를 ②라고 하겠습니다.

이제 ⓒ의 부분수열을 생각해보겠습니다.

다음을 구해주면 됩니다.

A^B^C + B^C + C

이때 C = 0^C이므로 아래와 같이 써보면

 A^B^C + B^C + 0^C

^C를 밖으로 뽑아내 아래와 같이 쓸 수 있을것 같습니다.

(A^B + B + 0)^C = (② + 0)^C 

그런데  (A^B + B + 0)^C 는 분배법칙이 성립하지 않습니다. (괄호 안을 먼저 계산하면 안됨)

 (A^B + B + 0)^C ≠  A^B^C + B^C + C

그래서 결국은 각 항에 ^C를 모두 해줘야 할 것 처럼 보였습니다.

왜 계산 결과가 달라질까?를 고민해 봤는데, 이유는 자릿수 올림 때문이었습니다.

그래서 괄호안을 먼저 계산하되, 자릿수 올림은 하지 않기로 했습니다. 

즉, 010 + 011 + 001 = 022와 같이 생각하기로 했습니다. 이제 자릿수 올림은 없으므로 XOR되는 같은 자리의 값만 고민하면 됩니다.

예를 들어 (010 + 011 + 001) ^ 101 을 괄호 안부터 계산한다고 하면 022^101이 됩니다. 

022 ^ 101의 결과는 무엇일까를 고민해보니, 각 자리의 숫자가 의미하는 바가 무엇인지 생각하게 됐습니다.

각 자리의 숫자는 전체 항 중에서 해당 자리가 1인 숫자의 개수를 나타냈습니다. 

즉, 022를 살펴보면 전체 3개의 항 중에서 첫째자리가 1인 항은 2개, 둘째자리가 1인 항은 2개, 셋째자리가 1인 항은 0개 라는 의미입니다.

이제 022 ^ 101을 계산할 수 있게 됐습니다.

이때 주의할 점은 전체 3개의 항 중에서 첫째자리가 1인 항의 개수가 2개라는 의미는 반대로 첫째자리가 0인 항은 1개 있다는 뜻입니다.

따라서 2^1을 계산하면 1^1 + 1^1 + 0^1 = 0 + 0 + 1이 됩니다.

마찬가지로 2^0 = 1^0 + 1^0 + 0^0 = 1 + 1 + 0 = 2

마지막으로 0^1 = 0^1 + 0^1 + 0^1 =  1 + 1 + 1 = 3

따라서  022 ^ 101 = 321 이라고 할 수 있습니다.

(실제로는 괄호안의 1의 개수를 센 후 한꺼번에 XOR 하는거에 가까워서 위 수학식이 맞는지는 모르겠네요. 그냥 편의상 사용했습니다.)

위 식을 잘 살펴보면 전체 항의 개수가 T일 때

K^0 = K (1의 개수가 K개이고, 0과 XOR한 경우에는 1의 개수만큼 1이 만들어집니다.)

K^1 = T - K (1의 개수가 K개이고, 1과 XOR한 경우 0의 개수만큼 1이 만들어집니다.)

임을 알수 있습니다.

만약 D도 있다면,  A^B^C + B^C + C = ③으로 놓고 ③^D + D를 구하면 됩니다. 모든 부분 수열의 XOR합은 ① + ② + ③ + ④ + ... 를 해주면 되겠네요.

시간 복잡도는 전체 항의 개수 N에 각 원소의 최댓값이 10억이니까 10억을 2진수로 바꾸는걸 고려하면 O(Nlog10억)이 됩니다.

전 매번 자릿수 올림을 한후 전체합 갱신을 해줘서 좀 오래걸렸는데 마지막에 한꺼번에 해버리면 좀더 빨라질것 같네요.


blutics   5년 전

감사합니다!!!

blutics   5년 전

감사합니다. 해결됬습니다.

convolution이랑 연관있어서 fft 계속 팠는데

fft 없이 해결을 봤네요.

근데 https://www.hackerrank.com/cha... 여기보시면

fft중에 하나인 Fast Walsh–Hadamard Transform으로도 풀 수 있는 것 같은데....

음......좀 더 파봐야겠네요.


jh05013   5년 전

그건 XOR합의 전체 합이 아닌 각각의 XOR합이 등장하는 횟수를 구해야 되는 문제니까 그렇고, 이 문제는 그것보다 훨씬 쉽습니다.

jh05013   5년 전

FFT를 이해하는 것은 수학적 지식이 많이 요구되고, 그걸 이해해야 FWHT 등의 변형을 이해할 수 있습니다. 정말로, 정말로, 정말로 그 문제를 풀고 싶으시다면 먼저 FFT를 공부한 다음 다음 문제를 푸시는 것을 추천드립니다.

https://www.acmicpc.net/proble...

https://www.acmicpc.net/proble...

https://www.acmicpc.net/proble...

blutics   5년 전

아닛!!!! 감사합니다~~~!!

댓글을 작성하려면 로그인해야 합니다.