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

Fast Calculations
Posted by 198808xc 25 Aug 2012 23:26
Many people could find the formula, due to the inclusion-exclusion principle, but also many people could not find a proper method to calculate the formula, especially under module p.

In fact, you don't need to calculate the huge combination numbers, nor do you need to perform some complex operations such as integer factorization. All you need is to rewrite the formula, and make it easier for calculation under module p.

The formulation from inclusion-exclusion principle is:
R = SUM (i = 0 to n) : (-1) ^ n * [(n + i)! / 2 ^ i] * C(n, i)
where C(N, i) is the combination number, which is also the most difficult part in the formula.

The key to calculation is rewrite the whole term, not only the combination number:
[(n + i)! / 2 ^ i] * C(n, i)
= [(n + i)! / 2 ^ i] * [n! / i! / (n - i)!]
= [(n + i)! * n!] / [2 ^ i * i! * (n - i)!]
= [(n + i)! / (n - i)!] / 2 ^ i * [n! / i!]

Now, please note that, [(n + i)! / (n - i)!] could be recursively calculated: we need only to multiple (n + i) and (n + 1 - i) to the previous calculation result. Fortunately, there must be an even number in every pair of (n + i) and (n + 1 - i). So the increasing power of 2 could be also recursively canceled.
Finally, the term [n! / i!] is easily calculated.

Therefore, we solved the problem without a DIVISION calculation, which is hard to perform under module p.

Hope this will help.
Re: Fast Calculations
Posted by iamavalon 5 Oct 2012 19:30
nice xD
one problem is that not everyone got exactly that formula, but instead another version of it. the fact that in your version of the formula you can obtain f(n) recursively only by multiplying two terms by f(n-1) makes it much easier. of course from the formula that i found i can get to yours, but thats more subtle.