Skip to content

Instantly share code, notes, and snippets.

@onkar27
Last active July 26, 2019 19:04
Show Gist options
  • Save onkar27/ec1d6208fb4e4ca88fd6ff31e5860a32 to your computer and use it in GitHub Desktop.
Save onkar27/ec1d6208fb4e4ca88fd6ff31e5860a32 to your computer and use it in GitHub Desktop.
Iterative function to calculate power exponential and nCr implementation
ll power(ll x, ll y, ll p)
{
ll res = 1;
x = x % p;
while (y > 0)
{
if (y & 1)
res = (res*x) % p;
y = y>>1;
x = (x*x) % p;
}
return res;
}
ll modInverse(ll n, ll p)
{
return power(n, p-2, p);
}
ll nCr[5001][5001];
void pre()
{
ll i, j;
for (i = 0; i < 5001; i++)
{
for (j = 0; j <=i; j++)
{
if (j == 0 || j == i)
nCr[i][j] = 1;
else
nCr[i][j] = mod(nCr[i-1][j-1] + nCr[i-1][j],Mod-1);
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment