방금 풀었는데, 저는
{A, B, C} 에서 A ^ (B + C + B^C)를 빠르게 구할 수 없을까? 결합법칙은 성립하지 않는것 같은데?
를 고민해 봤어요
13710번 - XOR 합 3
늦어서 죄송합니다 ㅠㅠ 위에 답변 달때 문제를 착각했었네요. 아래는 제가 고민한 방법입니다.
처음에 (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억)이 됩니다.
전 매번 자릿수 올림을 한후 전체합 갱신을 해줘서 좀 오래걸렸는데 마지막에 한꺼번에 해버리면 좀더 빨라질것 같네요.
감사합니다. 해결됬습니다.
convolution이랑 연관있어서 fft 계속 팠는데
fft 없이 해결을 봤네요.
근데 https://www.hackerrank.com/cha... 여기보시면
fft중에 하나인 Fast Walsh–Hadamard Transform으로도 풀 수 있는 것 같은데....
음......좀 더 파봐야겠네요.
FFT를 이해하는 것은 수학적 지식이 많이 요구되고, 그걸 이해해야 FWHT 등의 변형을 이해할 수 있습니다. 정말로, 정말로, 정말로 그 문제를 풀고 싶으시다면 먼저 FFT를 공부한 다음 다음 문제를 푸시는 것을 추천드립니다.
https://www.acmicpc.net/proble...
댓글을 작성하려면 로그인해야 합니다.
blutics 5년 전
도저히 모르겠네요.
어떤 알고리즘으로 푸는 건지 알려주세요 ㅠ
fft로 푸는건가요??
fft 아닌거 같은데.....ㅠ