Hi
How to calcute c(n,r) modula p when p is prime.
1<= n,r<= 10^5.
please give me a algo with inverse number! (thanx a lot)
sorry for my poor english.

To find inverse number you can use Fermat's little theorem ( http://en.wikipedia.org/wiki/Fermat%27s_little_theorem ):
a^(p-1) mod p = 1
Multiply both parts of the equality by a^(-1):
a^(p-2) mod p = a^(-1)

Edited by author 08.02.2011 23:05

thanks for your answer,
 but how to use this for calcute C(n,k) ?

please answer to me.
thanks!!!

Let's make some denotations before starting. Let n! be up and k!*(n-k)! be down and c(n,k) be bc - short form of binomial coef, so we have up/down  = bc.
First af all, find the prime's degree both in up and down using Legendre's formula:
degree_of_prime_in_x! = x/prime +x/prime^2+ x/prime^3 and so on, while x>=next_deg_of_ prime. You see, it works very fast, in log(factorial_value) by prime base.
After that, we have two possible cases:
1) Degree of prime in up>the same thing in down;
It means that after reduction up and down on p^degree_of_down_part we have up = p^delta_degree*some_int1/some_int2 = bc, where both some_int1 and some_int2 DON'T divide p but fraction some_int1/some_int2 is an integer. Obviously, bc%p=0 in this case
 because bc%p = (int_result_of_fraction*p^some_degree)%p = some_remainder*0 = 0;
2) degree in up  = degree in down. So, up/down = (p^x*some_int1) / (p^x*some_int2) = bc;
After reduction on p^x we have some_int1 = some_int2*bc, where both of some_ints don't divide p or, in other words, gcd(p,some_int1) = gcd(p,some_int2)=1; some_int_1 and some_int2 denoted as si1 and si2 in the rest part of text because i'm too lazy=)
Let's take both part by modulo p:
si1%p = (si2%p)*(bc%p)   <=> si1%p = si2*answer_you_need, so, answer_you_need = si1%p*(1/si2%p) or answer_you_need=si1%p*(inverse_elem_to_si2_by_modulo_p);
Now we are ready to use Fermat's little theorem:
si2^p==si2(mod p), but we can use more stronger equation because gcd(si2,p)=1,as I mentioned 5 lines before.
Stronger eq:si2^(p-1)==1(mod p); Please, note that stronger version is allowed only when gcd(si2,p)=1 thats why we started from boring reduction of prime component!
we can divide both parts of comparison/equation/equivalence_relation on si2 and write something like that:
si2^(p-2)==1/si2(mod p); you can ask, why division is allowed here but just believe me, it's just rule which yo can find and read in internet. so 1/si2(mod p) is inverse_element, so answer_you_need = si1%p*(inverse_elem) = si1%p*si2^(p-2); If p is large you can use fast_exp; si1%p ans si2%p calculated in ~linear time via stupid for loop:
si1=1;

for(int i=2;i<=n;i++){
tmp=i;
  if(i%p==0){

   while(tmp%p==0) tmp/=p;
   // here tmp%p!=0 because while loop excluded p.

  }
  si1*=tmp;

si1%=p;
}
P.S This loop was written considered deg_in_up=deg_in_down because when d_in_up>in_down you may return zero, I explained why.
The same loop for si2 but you nedd 2 loops: i<n-r and i<r;

P.P.S Please, answer to my question here http://acm.timus.ru/forum/thread.aspx?id=25978&upd=634327602601135000 or just advise me how avoid problems with precision in double_variables binary_search




Edited by author 09.02.2011 23:55

Something like this:

int fact(int x, int mod) {
    if (x == 0) return 1;
    return (x * fact(x-1, mod)) % mod;
}

int pow(int x, int n, int mod) {
    if (n == 0) return 1;
    if (n % 2 == 0) {
        int tmp = pow(x, n/2, mod);
        return (tmp * tmp) % mod;
    }
    return (x * pow(x, n-1, mod)) % mod;
}

int c(int n, int k, int mod) {
    int up = fact(n, mod);
    int down = (fact(k, mod) * fact(n-k, mod)) % mod;
    int downInv = pow(down, mod-2, mod);
    return (up * downInv) % mod;
}

Wait... You have solved 290 problems, and you don't know how to calculate C(n,k)?

in my solved problem there is no need to calcute c(n,k) for n bigger than 50, and for this question i use dynamic programming.
thanks in advance and i dont forgot your help in my life ;D