Hello coders! let's suppose we have three numbers n,k,mod=1e9+7 where n,k<=1e9 how to calculate nCk %mod! any hint please! Thanks^__^

# | User | Rating |
---|---|---|

1 | Benq | 3796 |

2 | tourist | 3722 |

3 | Radewoosh | 3719 |

4 | ecnerwala | 3578 |

5 | ksun48 | 3462 |

6 | Um_nik | 3456 |

7 | maroonrk | 3445 |

8 | jiangly | 3431 |

9 | Petr | 3370 |

10 | scott_wu | 3350 |

# | User | Contrib. |
---|---|---|

1 | 1-gon | 208 |

2 | awoo | 186 |

3 | rng_58 | 184 |

4 | Errichto | 182 |

5 | SecondThread | 178 |

6 | Radewoosh | 177 |

7 | -is-this-fft- | 176 |

7 | maroonrk | 176 |

9 | Um_nik | 173 |

10 | antontrygubO_o | 170 |

Hello coders! let's suppose we have three numbers n,k,mod=1e9+7 where n,k<=1e9 how to calculate nCk %mod! any hint please! Thanks^__^

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/14/2021 22:37:25 (g2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

You can calculate N! in

`O(log(N))`

using Matrix Multiplication, then calculate`N! / [ K! * (N — K)! ] % mod`

How ? (only when mod is prime)thanks but how to calculate N! in log(n)?

If you can calculate

n! inO(log(n)) then you have solved prime checking inO(log^{3}(n)) or something. See this.so we can calculate n! % mod only using linear solution?

See this. The main idea is sqrt decomposition and Lagrange interpolation. The complexity is .

Thank you so much :)

Doesn't Wilson's theorem give a $$$\mathcal{O}(\log n)$$$ time primality check in that case?

lol no, how you can calculate (p — 1)! % p in log(n)?

The comment I was replying to said "

If you could compute $$$n!$$$in $$$\mathcal{O}(\log n)$$$ you'd have a $$$\mathcal{O}(\log^3 n)$$$ primality check". Note that no claim is made that there is a $$$\mathcal{O}(\log n)$$$ algorithm for computing the factorial.sorry for carelessness

Another approach is precalculate 10

^{6}!, (2·10^{6})!, ..., 10^{9}! locally and paste it in your code. Then you can easily calculate every factorial using 10^{6}multiplications.How about prime power? For example, mod = 289.

If mod is a prime, you can use Lucas theorem: https://en.wikipedia.org/wiki/Lucas%27s_theorem

Thanks.

Way 1:Precalculate the factorials. Then, use Fermat's Little theorem, which says that says that $$$a^{-1} \equiv a^{p - 2} \pmod{p}$$$. This allows us to sort of transform modular division into modulo multiplication and then some powers. The pre-computing factorial is $$$O(n)$$$, dealing with the denominator is $$$O(\log(N))$$$ if you use fast exponentiation.Way 2:Pascal's Identity. Straight forward dynamic programming. This is $$$O(n^2)$$$.Optimization:Use Lucas's theorem.I think you didn't realize that $$$n = 10^9$$$ which makes pre computing of factorials $$$O(n)$$$ is impossible within time and memory limit

I was speaking generally, which is why I included Way 2, which is clearly too slow. I think with Lucas's theorem, Way 1 would be sufficiently fast, though.

How would you optimize it using Lucas's theorem?

You can calculate C(n,k) = n! * reverse((n — k)!) * reverse(k!) which reverse(a) = power(a, mod — 2)

If you have enough memory, you can save first a! into an array