ilbppbli's blog

By ilbppbli, history, 5 weeks 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

 
 
 
 

»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

What's with the downvotes...

  • »
    »
    4 weeks 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.

  • »
    »
    4 weeks 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 :)

»
4 weeks 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.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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