숫자 n이 있다고 가정하고 1에서 n까지의 이진 표현을 하나씩 순서대로 연결하여 이진 문자열의 10진수 값을 찾아야 합니다. 답이 너무 크면 모듈로 10^9 + 7을 반환합니다.
따라서 입력이 n =4와 같으면 출력은 220이 됩니다. 왜냐하면 1에서 4까지의 이진 표현을 연결하면 "1" + "10" + "11" + "100" =110111000이 되기 때문에 이것은 이진입니다. 220의 대표자.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- ans :=1
- m :=10^9+7
- 2~n 범위의 i에 대해 다음을 수행합니다.
- ans :=shift as (i의 비트 길이) 횟수
- ans :=(ans+i) 모드 m
- 반환
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
def solve(n): ans = 1 m = (10**9+7) for i in range(2,n+1): ans = ans<<i.bit_length() ans = (ans+i) % m return ans n = 4 print(solve(n))
입력
4
출력
220