using System.Numerics;
public class EggChallenge
{
private static BigInteger mo = new BigInteger(998244353);
public static BigInteger Height(BigInteger n, BigInteger m)
{
return n == 0 || m == 0 ? 0 : BigInteger.Remainder(SumHeight(n+1, m), mo);
}
public static BigInteger SumHeight(BigInteger n, BigInteger m)
{
BigInteger BigInt = new BigInteger(1);
BigInteger BigIntegerSum = new BigInteger(0);
for(int i = 1; i < n; i++)
{
BigInt = BigInteger.Divide(BigInteger.Multiply(m + 1 - i, BigInt), (BigInteger)i);
BigIntegerSum = BigInteger.Add(BigIntegerSum, BigInt);
}
return BigIntegerSum;
}
}
C# supports operator overloading subject to some constraints, and BigInteger has all of the arithmetical operators implemented. So you can improve legibility a lot by using standard operators rather than BigInteger.OperatorName(foo, bar).
Local variables in C# normally begin with a lower case letter, so using upper case is not very helpful. In addition, BigInt doesn't tell me anything useful: I know that the type is BigInteger because I can see the declaration, but what does the variable mean?
Renaming and using overloaded operators I get rewritten code which IMO is easier to read:
BigInteger Height(BigInteger n, BigInteger m)
{
return n == 0 || m == 0 ? 0 : SumHeight(n + 1, m) % mo;
}
BigInteger SumHeight(BigInteger n, BigInteger m)
{
BigInteger term = 1;
BigInteger sum = 0;
for (int i = 1; i < n; i++)
{
term = (m + 1 - i) * term / i;
sum += term;
}
return sum;
}
I don't think the algorithm is what to improve has it seems to run at
O(n), but I could be very wrong.
I'm afraid that you are very wrong. The code is performing \$O(n)\$ arithmetical operations on BigIntegers, but an arithmetical operation on a BigInteger is not \$O(1)\$. The fundamental problem is this:
... SumHeight(n + 1, m) % mo;
It should instead be
... SumHeight(n + 1, m, mo);
with the % being applied regularly inside the loop:
for (int i = 1; i < n; i++)
{
term = (m + 1 - i) * term % mo;
term = ModDiv(term, i, mo); // I'll come back to this
sum += term;
}
return sum % mo;
The massive advantage is that you no longer need BigInteger: it suffices to use long (or maybe ulong: it's a matter of taste because 998244353 was chosen such that long would work in languages like Java which don't have ulong).
I infer from your comment on an earlier answer that you haven't studied modular arithmetic. This is quite understandable: I think it's safe to say that 99% of programmers will never use it in their careers. But although it is irrelevant for most line-of-business programming, it is quite important in code contests/challenges (interpreted broadly to include katas, Project Euler, etc.) because they frequently use modular arithmetic to make large test cases feasible. If you find katas either enjoyable or useful for your CV, it's probably worth your time to study.
The properties I'm relying on are (treating % as an operator on arbitrary-width integers and assuming that we're avoiding overflow, which is % Pow(2, IntegerTypeWidth)):
((a % m) + (b % m)) % m == (a + b) % m
((a % m) * (b % m)) % m == (a * b) % m
Now I can come back to modular division. Essentially ModDiv(term, i, mo) needs to calculate a modular reciprocal of i (i.e. j such that i * j % mo == 1) and then return term * j % mo. There is always such a j as long as it is coprime with mo, and 998244353 is deliberately chosen to be a prime number, deliberately chosen so that you can divide by any number which isn't a multiple of it. The standard approach to calculate a modular reciprocal is the extended Euclidean algorithm, and is described in so many millions of web pages that I won't try to give my own explanation here.
To wrap up the explanation, I must address a point raised by Rick Davin. If you rewrite SumHeight so that n and m are both long, how to handle the test case m = BigInteger.Pow(2, 200)? If we look at how m is used, it takes part in addition and multiplication. So the way to do this is to do the modulo in BigInteger and then cast to long:
long Height(BigInteger n, BigInteger m)
{
return n == 0 || m == 0 ? 0 : SumHeight((long)n + 1, (long)(m % mo), mo);
}
