N-초입방체는 0 to 2N – 1 까지 번호가 메겨진 2N 개의 노드가 있는 비순환 방향 그래프이며, 만약 x에서 y로 향하는 간선이 있다면, x < y 이며 x ^ y = 2p (^는 xor 연산자) 를 만족하는 음이 아닌 정수 p 가 존재하고 역 또한 성립합니다.
The N-hypercube is an directed acyclical graph with 2N nodes tagged with numbers from 0 to 2N
– 1 so that there is an arc from node x to node y if and only if x <
y and a non-negative integer p exists such that x ^ y = 2p (^ operator stands for bitwise xor).
N, M, K가 주어질 때 다음을 계산하세요. Given N, M and K, three positive integers, you are to compute:
N-초입방체에서 M 번 노드로 향하는 간선이 시작하는 노드 번호의 최댓값. The minimum label i of a node belonging to the N-hypercube that has an arc from i to M.
N-초입방체에서 M 번 노드에서 시작하는 간선이 향하는 노드 번호의 최소값. The minimum label j of a node belonging to the N-hypercube that has an arc from M to j.
N-초입방체에서 찾을 수 있는 K-길이의(K개의 간선을 포함하는) 경로의 개수. 값이 너무 클 수 있으므로, 개수를 100003으로 나눈 나머지를 계산하세요. The number of paths of length K (having K arcs) found in the
N-hypercube. Because this number may be quite large, you are to compute
the number modulo 100003.
입력
첫번째 줄은 N, M, K 순서대로 한 칸의 띄어쓰기로 분리되어 입력됩니다. The first line of the input contains three numbers N, M and K, each separated by one space.
출력
첫번째 줄에는 a번째 계산의 정답을 출력하세요. 두번째 줄에는 b번째 계산의 정답을 출력하세요. 세번째 줄에는 c번째 계산의 정답을 출력하세요 The first line of the output must contain a single number, the
answer for task a. The second line must contain a single number, the
answer for task b. The third line must contain a single number, the
answer for task c.
제한
2 ≤ K ≤ N ≤ 100,000
1 ≤ M ≤ 100,000,000
주어진 M에 대해, M번째 노드로 향하는 간선과 시작하는 간선은 각각 하나씩 존재함을 보장합니다. For any given number M, there is at least one arc leaving node M and one arc reaching node M.
c번째 계산의 정답은 경로의 개수를 100003로 나눈 나머지 입니다. The answer for task c must be computed modulo 100003.
^ 연산자는 xor 연산을 의미합니다. ^ operator stands for bitwise xor.
2chanhaeng 3년 전 1
초입방체
문제
The N-hypercube is an directed acyclical graph with 2N nodes tagged with numbers from 0 to 2N – 1 so that there is an arc from node x to node y if and only if x < y and a non-negative integer p exists such that x ^ y = 2p (^ operator stands for bitwise xor).
N, M, K가 주어질 때 다음을 계산하세요.
Given N, M and K, three positive integers, you are to compute:
The minimum label i of a node belonging to the N-hypercube that has an arc from i to M.
The minimum label j of a node belonging to the N-hypercube that has an arc from M to j.
The number of paths of length K (having K arcs) found in the N-hypercube. Because this number may be quite large, you are to compute the number modulo 100003.
입력
첫번째 줄은 N, M, K 순서대로 한 칸의 띄어쓰기로 분리되어 입력됩니다.
The first line of the input contains three numbers N, M and K, each separated by one space.
출력
첫번째 줄에는 a번째 계산의 정답을 출력하세요. 두번째 줄에는 b번째 계산의 정답을 출력하세요. 세번째 줄에는 c번째 계산의 정답을 출력하세요
The first line of the output must contain a single number, the answer for task a. The second line must contain a single number, the answer for task b. The third line must contain a single number, the answer for task c.
제한
For any given number M, there is at least one arc leaving node M and one arc reaching node M.
The answer for task c must be computed modulo 100003.
^ operator stands for bitwise xor.
오류는 댓글에 남겨주시면 감사하겠습니다.