[Solved] Big limit combinatorics problem

Правка en5, от Chi, 2018-10-18 15:01:17

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 im Vietnamese, and i don't understand it either

Теги combinat

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en6 Английский Chi 2018-10-18 15:01:42 2 Tiny change: 'nd it is im Vietnames' -> 'nd it is in Vietnames'
en5 Английский Chi 2018-10-18 15:01:17 97
en4 Английский Chi 2018-10-18 15:00:23 9
en3 Английский Chi 2018-10-16 08:38:49 8 Tiny change: 'ither TLE too (or MRE), whatever' -> 'ither TLE or MLE, whatever'
en2 Английский Chi 2018-10-15 19:22:18 11 Tiny change: 's problem.' -> 's problem.\n\nThanks.'
en1 Английский Chi 2018-10-15 19:20:58 861 Initial revision (published)