gudrbscse   6달 전

헤비사이드 부분분수 분해법으로 구현하였는데,,

그 시간초과가 발생합니다. O(nm) 을 어떻게 줄일수 있을지를 모르겠네요..ㅠ

pichulia   6달 전

일단 int p(int a, int n);

이 함수 내용물을 O(lg n)으로 줄일 수 있습니다.

a^n mod m 을 O(lg n)만에 구하는 방법은 여기저기 많이 널려있을 테지만...일단 현제 코드에 맞게 변형해보자면


int p(int a, int n) {
    long long int t = 1;

    long long int z = a;

    while(n) {

        if(n%2){ t = (t*z)%1000000007;}

         z = (z*z)%1000000007;

    }
    return t;
}


일단 이렇게 고쳐도 "틀렸습니다"를 받게 되는데요...

sum *= ((double)u / d);

이 부분에서 정확도와 관련한 어떤 문제가 발생하지 않을까 하는 조심스러운 추측을 합니다..

gudrbscse   6달 전

어떤 문제가 발생하는 건지를 모르겠네요 ㅠ

댓글을 작성하려면 로그인해야 합니다.