forget_it's blog

Please help me in following.... mathematical concept — educational round 83 D
By forget_it, history, 4 years ago, In English

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

  • Vote: I like it
  • +2
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

I have implemented the same logic and got AC

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

    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 ??...

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

      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

      → Reply