The 22th Japanese Olympiad in Informatics Final Round Online ContestThe 22th Japanese Olympiad in Informatics Final Round Online Contest Home / The 22th Japanese Olympiad in Informatics Final Round Online Contest Overview Japanese version is available here. The 22th Japanese Olympiad in Informatics Final Round Online Contecontests.ioi-jp.org중국의 csy2005(Codeforces, AtCoder)라는 분이 500점으로 OC 1등을 차지했..

문제 링크 질문은 언제나 환영입니다. 풀이 더보기 지그재그의 조건을 생각해보자. 지그재그는 인접합 2~3개 정도의 원소만 보면 된다. 지그 다음에는 재그 그 다음에는 지그... 따라서 지그 또는 재그의 상태끼리 다 묶어서 관리하면 계산량이 $10^{500}$ 가까이에서 훅 줄어서 reasonable해 질 것이다. 그리고 지그와 재그를 표현함에 있어서 그 자리의 숫자들도 당연히 관리해야 할 것이다. 지그/재그 상태와 자리 숫자가 같아도 몇 자릿수인지에 따라 달라질 것이다. 그래서 자릿수도 관리하고... $M$의 배수라고 하니까, 좀 고민하다가 보면 $M$으로 나눈 나머지를 잘 써주면 좋겠다 싶은데, 이 정보도 함께 관리하면 되겠다. $U(i,j,k):=i$자리에서 증가세로 숫자 $j$에 도달했을 때, 나머..