saurabh247's blog

By saurabh247, history, 5 years ago, In English

Problem link https://codeforces.net/contest/615/problem/D

My Submission https://codeforces.net/contest/615/submission/78009885

Can anyone please tell why my submission is getting WA . I have read the editorial and got the solution but i would like to know why this approach is not working. I am trying this for a long time and have no clue. Please help!!

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by saurabh247 (previous revision, new revision, compare).

»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Look at comments : https://codeforces.net/blog/entry/22658?#comment-271616 and https://codeforces.net/blog/entry/22658?#comment-271626.

you are calculating power(p, k) under modulo 1e9+7 (M). However while calculating k you are taking k = k%M. Instead you have to take k%(M-1) due to fermat's theroem.

For calculating, $$$P = ((cnt[1]+1)*(cnt[2]+1)*(cnt[3]+1)*....*(cnt[k]+1)) * (cnt[i]+1)^{-1} mod (M-1)$$$ , you can precompute : $$$lmul[i] = (cnt[1]+1)*(cnt[2]+1)*(cnt[3]+1)*....*(cnt[i]+1)$$$ $$$rmul[i] = (cnt[i]+1)*(cnt[i+1]+1)*(cnt[i+2]+1)*....*(cnt[k]+1)$$$

Now, $$$P = lmul[i-1] * rmul[i+1]$$$

Now your $$$k = P*((cnt[i]*(cnt[i]+1))/2)mod(M-1)$$$

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thnx but I still have a query .. As you said that for calculating k i have to take mod with (M — 1). I took mod with (M — 1) with my previous submission and got again WA My submission https://codeforces.net/contest/615/submission/78094420 .. I want to know why this is happening ? could u pls help

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      You are finding inverse of 2 mod (M-1). However it will not exist. Calculate k like this : $$$k=P∗((cnt[i]∗(cnt[i]+1))/2)mod(M−1)$$$

      Here before diving by 2, the numerator will be even. So mod (M-1) can be found after dividing by 2.

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        got it thank you brother I think it's because gcd(2 , 1e9 + 6) is equal to 2.