| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 85 | 44 | 24 | 43.636% |
AI가 세상을 휩쓸고 있는 가운데, LG전자는 AI CPU를 탑재한 노트북 LG 그램, 방의 환경을 스스로 조절하는 에어컨 휘센 AI AIR 등 AI를 활용한 차세대 전자기기를 만들기 위해 전력을 다하고 있다.
이런 고성능 AI 연산을 가능케 하는 기술로 멀티스레딩을 빼놓을 수 없다. 스레드는 프로그램 내에서 병렬로 돌아가는 실행 경로를 의미하며, 컴퓨터는 이를 통해 여러 작업을 동시에 수행함으로써 효율성을 향상한다. 하지만 스레드 간에 공유되는 자원이 있을 때에는 동기화를 주의 깊게 맞춰 줘야 한다.
스레드를 막 배운 프로그래머 리프는 LG 그램을 열고, 정수형 변수 x를 선언한 뒤 $N$개의 스레드가 x = x + 1이라는 명령문을 실행하는 프로그램을 작성했다. x에 1ドル$을 더하는 이 명령문을 실행하려면 x를 읽는 작업과 x를 쓰는 작업이 필요한데, 사실 이 둘은 동시에 일어나는 게 아니라 다음 순서대로 일어난다.
x의 값을 읽고 기억한다.x에 덮어씌운다.문제는 한 스레드의 절차 1과 2 사이에 다른 스레드가 간섭할 수 있다는 것이다. x의 초기값이 0ドル$이라고 할 때, 스레드 A와 B가 각각 절차 1을 진행하면 둘 다 0ドル$이란 값을 읽고 기억한다. 그 후 A와 B가 각각 절차 2를 진행하면 둘 다 x에 1ドル$을 쓰기 때문에, x의 값은 1ドル$이 된다. x를 1ドル$ 늘리는 명령이 두 번 실행되더라도 x가 2ドル$만큼 늘어나지 않을 수도 있는 것이다. 그래서 프로그램을 돌렸더니 x의 값이 $N$이 아닌 다른 수가 되어 있는 것을 본 리프는 깜짝 놀랄 수밖에 없었다.
이제 우리가 LG 그램이 되어 스레드 $N$개를 원하는 순서로 실행시킬 수 있다고 생각해 보자. 각 스레드는 정확히 두 번 실행되어야 한다. 스레드가 처음 실행될 때는 절차 1을 진행하고, 두 번째로 실행될 때는 절차 2를 진행한다. 이렇게 스레드를 실행시키는 경우의 수는 $\frac{(2N) !}{2^N}$이다. 그렇다면 x의 초기값이 0ドル$이라고 할 때, $N$개의 스레드가 실행을 마쳤을 때 나올 수 있는 x 값의 분포는 어떻게 될까?
첫 줄에 정수 $N$이 주어진다. (1ドル\leq N\leq 200,円 000$)
첫 줄에 가능한 x 값의 개수 $M$을 출력한다.
다음 줄부터 $M$개의 줄에 걸쳐 한 줄에 하나씩, 가능한 x 값 하나와 그 x 값이 나오는 스레드 실행의 경우의 수를 998ドル,円 244,円 353$으로 나눈 나머지를 출력한다. 가능한 x 값이 여러 개라면 x 값에 대한 오름차순으로 모두 출력한다.
998ドル,円 244,円 353=119\times 2^{23}+1$은 소수이다.
2
2 1 4 2 2
100
100 ... [89 more lines] ... 90 729889561 91 145721628 92 477239109 ... [8 more lines] ...
두 스레드를 A와 B라고 하고, 각 스레드의 스텝을 A1과 A2, 그리고 B1과 B2라고 하자. 스레드 실행 순서에 따른 x 값은 다음과 같다.
예제 2는 출력이 너무 길어 일부만 표시하였다. 실제로는 줄을 생략하지 않고 모두 출력해야 한다.
University > 전국 대학생 프로그래밍 대회 동아리 연합 > UCPC 2024 K번