시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 (추가 시간 없음) | 512 MB | 261 | 97 | 89 | 41.981% |
많은 프로그래밍 언어에서는 정수에 대해 다음과 같은 두 개의 단항 연산을 지원한다.
-x
: x
의 부호를 바꾼다. x
의 값이 0인 경우는 값이 변하지 않는다.~x
: x
의 모든 비트를 뒤집는다. 예를 들어 x
의 2진수 표현이 0000 1010
일 경우 ~x
는 1111 0101
이 된다.편의상 이 문제에서 다루는 프로그래밍 언어에서는 정수를 무한히 많은 비트로 표현하며, 음수를 나타낼 때 2의 보수 표현법(음수를 표현할 때 무한히 큰 2의 거듭제곱에서 그 수를 뺀 값으로 나타내는 표현법)을 쓴다고 가정한다. 이때 ~x
의 연산 결과는 -x-1
과 같다.
연산 | 10진법 | 2진법 |
x |
10 |
0000 1010 |
-x |
-10 |
1111 0110 |
~x |
-11 |
1111 0101 |
x
의 값이 10인 경우의 예시
정수 0에 위의 두 연산을 총 N번 적용해서 정수 M을 만들고자 할 때, 가능한 연산 순서의 가짓수를 구하여라.
첫 줄에 연산 횟수를 의미하는 정수 N과 만들고자 하는 정수 M(0 ≤ N ≤ 300,000, -300,000 ≤ M ≤ 300,000)이 주어진다.
첫 줄에 정수 0에 N번의 연산을 적용하여 M을 만드는 방법의 가짓수를 998,244,353으로 나눈 나머지를 출력한다.
4 0
6
7 -3
7
1번 예시의 경우 ----0
, --~~0
, -~~-0
, ~--~0
, ~~--0
, ~~~~0
의 6가지 경우가 존재한다.
2번 예시의 경우 --~-~-~0
, ~---~-~0
, ~-~---~0
, ~-~-~--0
, ~-~-~~~0
, ~-~~~-~0
, ~~~-~-~0
의 7가지 경우가 존재한다.
University > 서울대학교 > 2018 서울대학교 프로그래밍 경시대회 > Division 1 E번