ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1747. Kingdom Inspection

i've found the formula - how compute it by modulo?
Posted by Baurzhan 28 Mar 2010 22:37
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?
Posted by RIPatti [Ufa] 27 Apr 2010 13:59
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?
Posted by iamavalon 30 Oct 2011 07:06
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.