mod 뻘글

  • 일루
    일루

    어제 srm 코드와 관련해 질문합니다. 하드에서 가져온거긴 한데 사실 내용은 별로 안중요하고..

    inner-most loop에서 % operator가 시간 소모가 심할 것 같아서 비교문으로 바꿔서 구현했습니다.

    const int mmod = 1000000007;

          for (int k=0; k<2*M; k++) {
            int next_k = k+1;
            if (next_k == 2*M) next_k = 0;
            dp[i+1][j+1][next_k] += dp[i][j][k];
            if (dp[i+1][j+1][next_k] >= mmod) dp[i+1][j+1][next_k] -= mmod;
          }

    헌데 나중에 체크해보니 다음 코드와 실행 시간 차이가 거의 없더군요.

    const int mmod = 1000000007;

          for (int k=0; k<2*M; k++) {
            int next_k = k+1;
            if (next_k == 2*M) next_k = 0;
            dp[i+1][j+1][next_k] += dp[i][j][k];
            dp[i+1][j+1][next_k] %= mmod;
          }

    왜 그럴까요?


    10년 전
1개의 댓글이 있습니다.
  • Being
    Being

    신기하네요. 컴파일된 어셈 코드를 볼 수 있다면 좋겠네요~


    10년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.