20669번 - Close to You
대회때도 똑같이 풀었는데 왜틀렸는지 ㅠㅠ
저도 분할정복을 이용했는데 시간초과가 뜨네요...
A + A^2 + ... + A^2n = (1 + A^n)(A^n + ... + A) 를 이용하는 것 아닌가요??
여기에서 A^n을 구하는 것도 분할 정복을 이용해서 구현했습니다.
혹 더 최적화시키는 방법이 있나요?
저도 같은 방법으로 풀었습니다 코드를 보니 필요없는 나머지 연산이 많아서 시간초과가 나는 것 같습니다
곱 : a += b*c%mod; if (a>=mod) a-=mod;
합 : a += b; if (a>=mod) a-=mod;
이런식으로 짜면 아마 시간내에 돌아갈거예요
그리고 메모리가 넉넉해서 행렬 10000개를 메모이제이션 하면 더 줄일 수 있긴 합니다..
아ㅠㅠ 나머지 연산으로도 시간초과가 나는군요.. 감사합니다!!
댓글을 작성하려면 로그인해야 합니다.
shjohw12 3년 전
대회때도 똑같이 풀었는데 왜틀렸는지 ㅠㅠ