0
$\begingroup$

I'm trying to solve this problem - https://codeforces.com/problemset/problem/711/E

I've already found and proved that the result is equal to: $$ 1 - \frac{2^n (2^n - 1) \cdots (2 ^ n - k + 1)}{2^{nk}}. $$ Now I need to compute it, and it's hard as $n$ and $k$ could both be as large as $10^{18}$. Computing $2^{nk}$ is easy. But I have a problem with this factorial. Result, of course, only need to be found modulo $10^6 + 3$.

EDIT:

Note that A and B must be coprime before their remainders modulo $10^6 + 3$ are taken.

Improve this question
$\endgroup$
  • $\begingroup$ If $k \geq 10^6 + 3$ then the answer is simply $1$. Otherwise, compute $a=2^n \bmod 10^6+3$ as usual, and then multiply $a(a-1)\cdots(a-k+1)$, at most $10^6 + 2$ factors. $\endgroup$ – Yuval Filmus Jan 13 at 18:46
  • 2
    $\begingroup$ By the way, I don't see any factorial in this post. $\endgroup$ – Yuval Filmus Jan 13 at 18:46
  • 1
    $\begingroup$ This will probably help you: cp-algorithms.com/algebra/factorial-modulo.html $\endgroup$ – Dmitry Jan 13 at 19:13
  • 1
    $\begingroup$ @Dmitry Not really. If you try to compute $2^n!/(2^n-k)!$, you will just get $0/0$. $\endgroup$ – Yuval Filmus Jan 14 at 7:53
  • $\begingroup$ The numerator is just $0$ unless $k$ is smaller than the modulus, let's call it $m$. In the latter case, you can multiply the $k<m$ terms modulo $m$ directly. $\endgroup$ – Emil Jeřábek Jan 14 at 9:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.