iliketrains42's blog

How to find nCr for big numbers, quickly and effectively?
By iliketrains42, history, 7 months ago, In English

https://tlx.toki.id/problems/bnpchs-2023-final/B

This question requires you to calculate the combination of two numbers where one ranges from 1 to 100 and the other from 1 to k.

They have also asked to mod the final answer by 1e9+7. How to write code in cases like these?

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

»
7 months ago, # |
  Vote: I like it +10 Vote: I do not like it

here ya go: https://cp-algorithms.com/combinatorics/binomial-coefficients.html

→ Reply
»
7 months ago, # |
← Rev. 2   Vote: I like it -38 Vote: I do not like it

int N_Choose_K(int n, int k, int mod) {

if(k == 1) return n;
    if(n-k == 1) return n;
    if(n == k) return 1;
    return (N_Choose_K(n-1,k,mod) + N_Choose_K(n-1,k-1,mod)) % mod;
}
→ Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

https://github.com/sreedhar3210/CP-snippets/blob/main/Combinatorics%20and%20fast%20power

you can refer this code snippet

→ Reply