Number theory (POWPOW2 spoj)

#1

how to compute 2nCn mod 1681 where n<=10^5

#2

int nCrModp(int n, int r, int p)
{
// The array C is going to store last row of
// pascal triangle at the end. And last entry
// of last row is nCr
int C[r+1];
memset(C, 0, sizeof©);

C[0] = 1; // Top row of Pascal Triangle 

// One by constructs remaining rows of Pascal 
// Triangle from top to bottom 
for (int i = 1; i <= n; i++) 
{ 
    // Fill entries of current row using previous 
    // row values 
    for (int j = min(i, r); j > 0; j--) 

        // nCj = (n-1)Cj + (n-1)C(j-1); 
        C[j] = (C[j] + C[j-1])%p; 
} 
return C[r];

}

n = 2n p = n

#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.