저도 분할정복을 이용했는데 시간초과가 뜨네요...

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개를 메모이제이션 하면 더 줄일 수 있긴 합니다..

아ᅲᅲ 나머지 연산으로도 시간초과가 나는군요.. 감사합니다!!