Chi's blog

[Solved] Big limit combinatorics problem
By Chi, history, 6 years ago, In English

Theres a problem from the The ICPC 2018 — Vietnam Central Provincial Contest that supposedly involves some combinatorics (The problem is here)

I originally planned to count the ways to break N/K into sum of at most M numbers, and then count the number of permutations of the children for each ways, and then use binpow to calculate total_ways % 1e9+7 (probably the first thing you would think of when you see the problem). But the limit was so high that i will have to choose between ridiculously long running time or using bignum (which can cause either TLE or MLE, whatever comes first.)

So it would be better if i could have an O(1) or an O(log N/K) solution for this problem.

Thanks.

Edit: the editorial is 4 pages long and it is in Vietnamese, and i don't understand it either

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

Comments Comments (6)
| Write comment?
»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

What's with the downvotes...

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

    Here you go friend :) an upvote for you! feel better, life isn't about the arrows.

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

    i just don't know why people don't like me asking questions, otherwise its fine :)

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

Just do combinatorics with big integer class, it only adds a linear factor.

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

    I'll try that. Thank you

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

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

→ Reply