What kind of Hash codes did U use?

Really good hint! Thanks!

thanks for advice, but it seems impossible for me to use long long because my aim is not submit 1503 problem, but care about cases when coefficients of polinomial is large enough - 10^20,10^30 - i need it in my work.Long long doesn't  allow to store such large numbers as I need. Also, I red in the forum that somobody accepted this problem with algorithm similar to mine, so my approach is correct but has some troubles with precision. Anyway, a lot of thanks for advice!

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;
}