히농의 잡합다식

한 1주일동안 고생한 문제라서, 까먹기 전에 풀이를 정리해두고자 합니다.저는 다이아1 티어를 줬지만, 저의 억울한 마음도 조금 담겨있기 때문에 과평가된 점이 있을 수도 있는 점 참고바랍니다.추가로, 마지막에 증명 없이 그냥 "이게 왜 됨?" 하면서 푼 내용이 있다는 점 역시 참고바랍니다. 문제 링크 : https://boj.ma/34279/t 34279번: Permutation Game boj.ma 문제를 요약하면, 길이 $n$ 짜리 permutation 와 노드 $m$ 개짜리 연결 그래프를 이용해 앨리스랑 밥이 게임을 하는 그런 문제입니다.앨리스는 밥한테 [0 $n$) 사이의 서로 다른 정수 $m$ 개를 줍니다. 그럼 밥은 그래프에서 간선을 하나 선택합니다. 간선의 양 끝 노드 번호가 $u$. $v$ ..

문제 링크 : https://boj.ma/34170/t 34170번: NP-Hard? NP-Complete? boj.ma 문제를 요약하면 $nCi (0 \le i \le n)$ mod $p^k$ == 0 인 i 의 개수를 세는 문제이다. subtask1 은 단순히 n+1 을 출력하면 된다.subtask2, subtask4 는 뤼카의 정리 를 이용하면 쉽게 풀 수 있다.간단하게 요약하면, n 을 p 진법으로 나타낸 수 {$n_0 n_1 n_2 ... n_r$} 에 대해서, ($n_i$ 는 $p^i$ 번째 자리수)$n_0 C i (0 \le i \lt p) \neq 0$ 인 i 의 가짓수는 $n_0 + 1$ 개, $n_1 C i (0 \le i \lt p) \neq 0$ 인 i 의 가짓수는 $n_1 + ..

안녕하세요. 원래는 한동안 PS 를 접고 뒷방늙은이로 평화롭게 살고 있었는데,메이플컵이 2회를 연다는 소식을 듣고, 메이플스토리2 유저로서 가만히 있을 수 없었습니다. 메컵콩 메이플스토리2 컨셉의 문제를 출제해도 된다는 허락을 받고, 몇 가지 문제를 제시했는데, 어쩌다보니 모두 채택되어서 3문제나 출제하게 되었습니다. 나름 인생의 1/10 넘게 투자한 게임이라서 애정을 가지고 있었고, 올해 25년 5월 29일을 기점으로 서비스종료가 예고되어있어, 지금이 아니면 관련 컨셉으로 문제를 더이상 출제할 수 없을 것 같았기에, 추모의 마음을 담아서 문제를 만들었습니다. C. 파이널 서바이버 "파이널 서바이버 게임에서 1,000 회 우승하기" 라는 도전과제가 있었습니다. 보통 저같은 사람은 일 하면서 잠수를 타다..