문제 링크https://www.acmicpc.net/problem/1010 다음과 같은 그림에서 서쪽 사이트의 개수만큼 다리를 지으려 할 때 겹치지 않게 다리를 모두 지을 수 있는 경우의 수를 구해야 한다. 다리끼리는 서로 겹쳐질 수 없다라는 조건이 있다. 이런 경우는 가능하지만 이런 경우는 불가능하다는 것이다. 서쪽 사이트의 집합을 $A$, 동쪽 사이트의 집합을 $B$라 하면 $1 \leq i, j \leq N$ 인 $i,\,j$와$1 \leq x, y \leq M$ 인 $x,\,y$에 대해 $A[i]$와 $B[x],\,A[j]$와 $B[y]$가 연결된다면 항상 $i
문제 링크 https://www.acmicpc.net/problem/12888 간단해 보이니까 머리를 싸매고 잘 생각해보자.. 어... 음... 헷갈린다. 이럴땐 그림판으로 그림을 그려보면 된다. 와! 규칙을 찾았다! $i$가 홀수일 때 $d[i] = (d[i-1] - 1)*2 + 1 = d[i-1]*2 - 1$ $i$가 짝수일 때 $d[i] = d[i-1]*2 + 1$ 그대로 코드로 옮기면 된다. 단, $0 \leq n$이므로 $n = 0$인 경우도 구해줘야 한다. 답이 나올 수 있는 범위는 long long 범위인 것도 확인하자. 정답 코드
문제 링크 2018/07/26 추가내용.참고) post-order대신 pre-order로 순회 해도 같은 효과를 볼 수 있으며, 코드를 조금 더 편하게, 더 직관적으로 짤 수 있다. pre-order로 순회하는 코드는 여기를 참고하자. 1번 정점을 루트로 하는 트리가 주어지고, M개의 질의가 주어졌을 때 다음과 같은 명령을 실행한다. 1 x꼴로 주어지는 질의에는 정점 x를 포함한 x의 모든 자손들의 가중치를 전부 XOR한 값을 출력.2 x y꼴로 주어지는 질의에는 정점 x를 포함한 x의 모든 자손들의 가중치에 각각 y를 XOR함 . 얼핏 봐선 그냥 하면 되는거 아닌가 싶겠지만 범위가 굉장히 크다.정점의 수 N과 질의의 수 M에 대해$(1\leq N \leq 100,000)$, $(1\leq M \leq ..