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 | tourist | 3771 |

2 | jiangly | 3688 |

3 | Um_nik | 3539 |

4 | slime | 3498 |

5 | djq_cpp | 3486 |

6 | MiracleFaFa | 3466 |

7 | ksun48 | 3452 |

8 | Radewoosh | 3406 |

9 | greenheadstrange | 3393 |

10 | xtqqwq | 3382 |

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

1 | -is-this-fft- | 183 |

2 | awoo | 181 |

3 | YouKn0wWho | 177 |

4 | Um_nik | 175 |

5 | dario2994 | 172 |

6 | Monogon | 171 |

7 | adamant | 168 |

8 | maroonrk | 167 |

9 | antontrygubO_o | 166 |

10 | errorgorn | 164 |

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-2022 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/10/2022 20:21:39 (j3).

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