Currently I'm solving an interesting performance variant of the egg dropping problem from codewars for which I need your help. The following equation is given: \begin{equation} f(d,n) = \sum_{i=1}^{n}{d \choose i} \end{equation}
- d represent the number of tries
- n represents the number of eggs
$f(d,n)$ calculates the maximum skyscrapper height (in floors), in which it is guaranteed to find an exactly maximal floor from which an egg won't crack.
Now the twist: Calculates the maximum skyscrapper height (in floors), in which it is guaranteed to find an exactly maximal floor from which an egg won't crack. But this time:
- d $\leq 100000$ and n $\leq 800000$
or
- $d \leq 2^{200}$ and n $ \leq 3000$
Due to these huge numbers it is required to calculate the result $\mod 998244353 $. This gives us the following formula:
\begin{equation} f(d,n) = \sum_{i=1}^{n}{d \choose i} \mod 998244353 \end{equation}
Now we can utilise the Lucas Theorem in order to speed up the calculation: \begin{align*} \sum_{i=1}^{n}{d \choose i} \equiv \sum_{i=1}^{n} \prod_{j=0}^{k} {d_{j} \choose i_{j}} \mod 998244353 \end{align*}
This will only improve computation performance if $d > 998244353 $ for example:
- $n=2$
- $d=160693804425899027554196$
\begin{align} \textstyle f(d,n) &\equiv {161259 \choose 0} * {536078175 \choose 0} * {736559690 \choose 1} + {161259 \choose 0} * {536078175 \choose 0} * {736559690 \choose 2} \mod 998244353 \\ &\equiv {736559690 \choose 1} + {736559690 \choose 2} \mod 998244353 \end{align} This reduces the binomial coefficient, however the computational costs are still way too high. Do you have any hints on how to speed up computation ?
Thank you very much
