[BOJ] 27981번 압도적 XOR 수

https://www.acmicpc.net/problem/27981

 

 

답

$N$보다 큰 $2$의 제곱수 중 가장 작은 값을 $2^n$이라 하자. $P=2^a$이라 하자.

$ \sum\limits_{a=1}^n\max(0,\min(P-1,N)-\lfloor\frac{(P-1)(2^K-1)}{2^K}\rfloor) \\=\min(n,K)+2^{n-min(n,K)}-2+\max(0,\ N-2^n+1+2^{\max(0, n-K)}) $

 

풀이

$A\ge B\times(2^K-1)$를 만족하는 $A$의 개수를 구해야 한다.

 

$1\le A\le N \\A\le P-1 $

이므로 $A\le\min(P-1,N)$

 

$B=(P-1) \oplus A=(P-1)-A$

$A\ge B\times(2^K-1)=(P-1-A)(2^K-1)=(P-1)(2^K-1)-A(2^K-1)$

$A+A(2^K-1)=2^KA\ge (P-1)(2^K-1)$

$ A\ge \frac{(P-1)(2^K-1)}{2^K}>\lfloor \frac{(P-1)(2^K-1)}{2^K}\rfloor $

 

$N$보다 큰 $2$의 제곱수 중 가장 작은 값을 $2^n$이라 하자. $P=2^a$이라 하자.

$1\le a \le n$

$ \lfloor \frac{(P-1)(2^K-1)}{2^K}\rfloor<A\\A \le\min(P-1,N) $

이므로 각각의 $a$에 대하여 $A$의 개수는 $ \max(0, \min(P-1,N)- \lfloor\frac{(P-1)(2^K-1)}{2^K}\rfloor)$개이다.

$A$의 개수는 $ \sum\limits_{a=1}^n\max(0,\min(P-1,N)-\lfloor\frac{(P-1)(2^K-1)}{2^K}\rfloor)$개이다.

 

정답 코드는 다음과 같다.

N, K = map(int, input().split())
n = N.bit_length()
print(sum(max(0, min((1<<i)-1, N)-((1<<i)-1)*((1<<K)-1)//(1<<K))for i in range(1, n+1)))

 

 

위 식의 시그마를 없애보자.

우선 다음 부등식들이 성립한다.

$2\le 2^a\le 2^n \\ 1\le a\le n \\ 2^{n-1}\le N\le 2^n-1$

 

다음 두 부등식을 $a$의 범위에 따라 변형하자.

$A\ge \frac{(P-1)(2^K-1)}{2^K}=P-1-\frac{P-1}{2^K} \\A \le\min(P-1,N)$

 

첫번째 부등식

$a\le K$일 때는 $0<\frac{P-1}{2^K}<1 $

 (증명)

$2\le P=2^a\le 2^K \\ 1\le P-1\le2^K-1<2^K \\ 0<\frac{1}{2^K}\le\frac{P-1}{2^K}<1 $

이므로 $A\ge P-1-\frac{P-1}{2^K}>P-2$이다.

$a>K$일 때는 $A\ge P-1-\frac{P-1}{2^K}=P-1-2^{a-K}+\frac{1}{2^K}>P-1-2^{a-K}$이다.

 

두번째 부등식

$a<n$일 때는 $P-1=2^a-1<2^n\le N$이므로 $A\le\min(P-1,N)=P-1$이다.

$a=n$일 때는 $A<\min(P-1,N)=\min(2^n-1,N)=N$이다.

 

표로 정리하면 다음과 같다.

	$a\le K$	$a>K$
$a<n$	$P-2<A\le P-1$	$P-1-2^{a-K}<A\le P-1$
$a=n$	$$2^n-2<A \\ A\le N$$	$$2^n-1-2^{n-K}<A \\ A\le N$$

 

 

(i) $n\le K$인 경우

$a\le n\le K$이므로 $P-2<A$이다.
(a) $1\le a<n$일 때 $A$의 개수를 구하자.

$a<n$이므로 표에 의해 $P-2<A\le P-1$
각각의 $a$에 대해 $A$의 개수는 $(P-1)-(P-2)=1$이다.
따라서 $A$의 개수는 $\sum\limits_{a=1}^{n-1}(1)=n-1$이다.

(b) $a=n$일 때 $A$의 개수를 구하자.

표에 의해 $2^n-2<A \\ A\le N$이다.
$ 2^n-2\ge N$이면 $A$의 개수는 $0$개이다.
$ 2^n-2<N$이면 $2^n-2<A\le N$이므로 $A$의 개수는 $N-(2^n-2)=N-2^n+2$개이다.
따라서 $A$의 개수는 $\max(0,N-2^n+2)$개이다.

(a), (b)에 의해 $A$의 개수는 $n-1+ \max(0,N-2^n+2)$개이다.
참고로 $N=2^n-1$인 경우 $A$의 개수는 $n$개이고, $2^{n-1}\le N\le 2^n-2$인 경우 $A$의 개수는 $n-1$개이다.

 

(ii) $K<n$인 경우

(a) $1\le a\le K$일 때 $A$의 개수를 구하자.

$a\le K<n$이므로 표에 의해 $P-2<A\le P-1$이다.
각각의 $a$에 대해 $A$의 개수는 $(P-1)-(P-2)=1$이다.
따라서 $A$의 개수는 $\sum\limits_{a=1}^K(1)=K$개이다.

(b) $K<a<n$일 때 $A$의 개수를 구하자.

$K<a<n$이므로 표에 의해 $P-1-2^{a-K}<A\le P-1$이다.
각각의 $a$에 대해 $A$의 개수는 $(P-1)-(P-1-2^{a-K})=2^{a-K}$개이다.
따라서 $A$의 개수는 $\sum\limits_{a=K+1}^{n-1}2^{a-K}=\frac{2(2^{n-K-1}-1)}{2-1}=2^{n-K}-2$개이다.

(c) $a=n$일 때 $A$의 개수를 구하자.

표에 의해 $2^n-1-2^{n-K}<A \\ A\le N$이다.
$2^n-1-2^{n-K}\ge N$이면 $A$의 개수는 $0$개이다.
$2^n-1-2^{n-K}< N$이면 $2^n-1-2^{n-K}<A\le N$이므로 $A$의 개수는 $N-(2^n-1-2^{n-K})=N-2^n+1+2^{n-K}$개이다.
따라서 $A$의 개수는 $\max(0,N-2^n+1+2^{n-K})$개이다.

(a), (b), (c)에 의해 $A$의 개수는 $K+ 2^{n-K}-2+\max(0,N-2^n+1+2^{n-K})$개이다.

 

(i) , (ii)에 의해 $A$의 개수는

$\begin{cases} n-1+ \max(0,N-2^n+2) &(n≤K)\\ K+2^{n-K}-2+\max(0,\ N-2^n+1+2^{n-K})&(K<n)\end{cases} \\= \min(n,K)+2^{n-min(n,K)}-2+\max(0,\ N-2^n+1+\lceil2^{n-K}\rceil) \\= \min(n,K)+2^{n-min(n,K)}-2+\max(0,\ N-2^n+1+2^{\max(0, n-K)})$개이다.

 

정답 코드는 다음과 같다.

N, K = map(int, input().split())
n = N.bit_length()
m = min(n,K)
print(m+(1<<(n-m))-2+max(0,N-(1<<n)+1+(1<<max(0,n-K))))