As the problem name suggest it is a combination type problem. In this problem there are n different objects, you want to take k of them. How many ways you can do it?
The formula for this problem is n! / ( r! * (n-r)! ).
To avoid time limit exit you need to pre-calculate the factorials from 1 to 106. Using Tabulation(Bottom Up Dynamic Programming) and modular arithmetic you can calculate it and keep it in an array. From that array you can get n!, r!, and (n-r)! very easily. As you need to perform modular operation with the result, you need to use modular inverse arithmetic operation. Using Extended Euclid you can find the inverse of r!(n-r)!. Then perform the modular multiplication operation with n! and the inverse you calculated. There is an important thing to consider that the Extended Euclid may return a negative value, so you need to handle it. By adding a multiple of mod value with this negative value you can handle it.
The function for the factorials will be like this,
long dp[1000000+1];
void factorials(){
dp[0] = 1;
dp[1] = 1;
for(long i=2; i<=1000000; i++){
dp[i] = ((dp[i-1]%MOD) * (i%MOD)) % MOD;
}
}
Here MOD = 1000003.
Here MOD = 1000003.
And the Extended Euclid function will look like this,
pair<long, long> EXTENDED_EUCLID(long a, long b){
if(b==0) return make_pair< long, long >(1,0);
else{
pair< long, long > d = EXTENDED_EUCLID(b, a%b);
return make_pair< long, long >(d.second, d.first - (a/b)*d.second);
}
}
Sign up here with your email
ConversionConversion EmoticonEmoticon