시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 1024 MB | 159 | 82 | 61 | 47.287% |
$x$좌표와 $y$좌표가 $0$ 이상 $2^N$ 미만 정수인 평면 좌표상의 모든 점에 각각 $x$좌표와 $y$좌표를 XOR한 값을 부여하자. 이처럼 어떤 데이터를 다른 데이터로 매핑하는 것을 해싱, 해싱된 데이터의 값을 해시 값이라고 한다.
값이 부여된 좌표 중 하나를 중복을 허용하여 균등한 확률로 $M$번 선택할 때, 같은 해시 값이 존재할 확률을 구하여라.
첫 번째 줄에 정수 $N$, $M$이 공백으로 구분되어 주어진다. $(1 \leq N \leq 20;$ $1 \leq M \leq 10^9)$
같은 해시 값이 존재할 확률이 $q\not\equiv 0 \pmod {10^9+7}$이고 서로소인 음이 아닌 두 정수 $p$, $q$에 대하여 $\frac{p}{q}$일 때, $p\times q^{-1}\bmod (10^9+7)$을 출력한다. $q^{-1}$은 $q$의 모듈러 곱셈 역원이다.
구해야 하는 확률이 항상 유리수임을 증명할 수 있다.
2 3
625000005
같은 해시 값이 존재할 확률은 $\frac{5}{8}$이다.
$8\times 125000001\equiv 1\pmod {10^9+7}$이므로 $8^{-1}\equiv 125000001\pmod {10^9+7}$이고, 답은 $5\times 125000001\pmod {10^9+7}=625000005$이다.