[Solved] Big limit combinatorics problem

Revision en6, by Chi, 2018-10-18 15:01:42

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.


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

Tags combinat


  Rev. Lang. By When Δ Comment
en6 English Chi 2018-10-18 15:01:42 2 Tiny change: 'nd it is im Vietnames' -> 'nd it is in Vietnames'
en5 English Chi 2018-10-18 15:01:17 97
en4 English Chi 2018-10-18 15:00:23 9
en3 English Chi 2018-10-16 08:38:49 8 Tiny change: 'ither TLE too (or MRE), whatever' -> 'ither TLE or MLE, whatever'
en2 English Chi 2018-10-15 19:22:18 11 Tiny change: 's problem.' -> 's problem.\n\nThanks.'
en1 English Chi 2018-10-15 19:20:58 861 Initial revision (published)