| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 220 | 110 | 85 | 46.448% |
$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$이다.