Блог пользователя forget_it

Автор forget_it, история, 5 лет назад, По-английски

Recently ,in educational round 83. In question D , i deduced a formula

for(i=n-1;i<=m;i++) { ans=ans+((nCr(i-1,n-2,mod))%mod; } And after that ans=(ans*pow(2,n-3,mod)*(n-2))%mod;

After looking for correct solution i found correct ans was nCr(m,n-1)*(n-2)*pow(2,n-3).

But later observe that for smaller test case my formula was working ,but giving Tle ,at larger tc.

So it that means expression nCr(m,n-1,mod) is equal to summation of nCr(i-1,n-2,mod) ; i range[n-1,m] .

If it is so ,can anyone help me to prove it..

here is my solution link 72867206

  • Проголосовать: нравится
  • +2
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

It gave TLE because you implemented that wrong. Have a look at my solution here

I have implemented the same logic and got AC

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Do i need to precalculate ,factorials and inverse modulus?? What part of my code is wrong?? , i designed code to calculate Combination using lucas concept? And later used fast power to calculate power.. , Any other suggesion ??...

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Yes you need to precalculate. You are calculating inverse modulus from 1 to r for every iteration where r = n — 2. So your complexity is m*n and hence the TLE