|
|
back to boardi've found the formula - how compute it by modulo? answer = all - 1_pair_bad+ 2_pair_bad + ...+(-1)^i_pair_bad = (2*n-2)!/2^(n-1) -> //all permutations of set{2,2,3,3,n,n}, //1 is the capital thats why don't included in set + sum(i=1,n-1)(-1)^i* //calculate bad permutations [C(i,n-1)*(2*n-2-i)!]/2^(n-1-i) this formula has 2 disadvantages: 1)calculating each Bad(i) requires O(i) time - counting factorial and degree, so, counting all Bad permutations will be TL. 2) division prevents us simply take each summand by modulo - even if a/b -> integer -> a/b != (a%p)/(b%p) --- We can avoid first disadvantage - Bad(i) can be counted in O(1) using bad(i-1) but modulo taking problem are still here. P/S I now that integer fraction's modulo can be found with fast_exponention and euler_function (like #140 in acm.mipt.ru) but i think it's not necessary here, i want solve this problem in linear time without number theory/ May be some reccurence exists? Does anybody know? Re: i've found the formula - how compute it by modulo? Simple linear reccurence without number theory exists. Re: i've found the formula - how compute it by modulo? Posted by svr 2 Apr 2011 12:43 Formula easy may be found in literature. Problem in computing binomials C[n,k] % p when n,k~10^5 and p is not prime. I think that formula C[n,k]=C[n,k-1]*(n-k+1)/k may be used but in realization: n-k+1=p1^(a1)*p2^(a2)...*pm^(am) and so for k also. In other words we are working in prime basis. In final answer all ai>=0 (because C[n,k] is int) and we don't need in finding h^(-1) mod p for some h. TLE...? C(n,k) has a long sequnce of prime factors for all k(I thought that more short) for example C(50,22)=(2^4)(7^2)(23^1)(29^1)(31^1)(37^1)(41^1)(43^1)(47^1). If find way to work with part (23^1)(29^1)(31^1)(37^1)(41^1)(43^1)(47^1) more quickly would be all Ok. Edited by author 04.04.2011 10:10 Re: i've found the formula - how compute it by modulo? if p1, p2, ..., pk are the prime factors of p, you can precompute the factorials of all numbers in the following form k = a * p1^e1 * ... pk^ek for each factorial, keep the value a mod p and the exponents. now, with gcd(a,p) = 1 you can use modular inverses and subtract exponents in order to obtain the correct value of C(n,k) modulo p. |
|
|