PROBLEM LINK:Author: Anton Lunyov DIFFICULTY:HARD PREREQUISITES:Binomial coefficients modulo prime powers, 128bit arithmetic PROBLEM:For the given n and R such that 0 ≤ R < 2^{n} you need to find the smallest K such that C(2^{n} − 1, K) mod 2^{n} = R, EXPLANATION:At first note that the problem requires to code 128bit arithmetic. This can be made by representing each number as a pair of 64bit values (lowest 64 bits and highest 64 bits) and then some routine job should be made to code all necessary operations. The only nontrivial one is multiplication. It can be made using only six 64bit multiplications (refer to the tester's solution). Actually only five is enough (refer to the author's solution). The first thing to notice is: It immediately follows from here that C(2^{n} − 1, K) is always odd. So if R is even then the answer is −1. At first we infer the following congruence from (1): Also we will need the following property: Then after some nontrivial analysis we get the following simple iterative routine that will find the answer:
The proof in Russian is contained here (pages 5758) and contains a lot of formulas. If you really want to see the proof in English, ask me in comment and maybe some day I will translate it :) Thus, the problem boils down to effective calculation of C(2^{n} − 1, K) modulo powers of two. But straightforward implementation of C(2^{n} − 1, K) using formulas (1) and (2), together with Note, that actually we can maintain value C(2^{j} − 1, K) mod 2^{n} in the loop of So At first we should calculate b(j, r, u) mod 2^{n−2} efficiently. Here main complication is that denominator could have even factors and we can't directly apply technique of inverse residues. To handle this we will use extended representation of integers in the form 2^{a} * b, where b is odd. So we could create a data structure that deals with this representation. Involving negative a and inverse residue technique for odd part of the number, we can handle noninteger numbers as well. Thus, to calculate b(r, j, u) we use the following plan:
Thus, the complexity of precalc is O(N^{3}) (we calculate O(N^{2}) values pseudo_fact[r][j] and each step requires finding inverse residue, which can be made in O(N) time) and calculation of all values b(r, j, u) for the given u is only O(N). Actually, saving inverses for numbers up to N in O(N^{2}) time we can speed up the precalc part to O(N^{2}), but even O(N^{3}) precalc is many times faster then some tricky precalc below. Now having values b(r, j, u) calculated we can find fact2(u) using r To speed up this part we can do the following. Note that we need to calculate powers of small fact2values in Thus precalculating such powers for each fact2(2 * j) (1 ≤ j ≤ 60) with constant H = 15, will speed up our solution in H = 15 times to O(N * N * N / H). But we can do even better. We can find prime factorization of fact2(u) and set up powers precalc only for odd primes up to 120 (there are only 29 of them). Then after calculation of b(r, j, u) we can do some simple O(N) loop to calculate degrees in factorization of fact2(u) and then calculate the answer as the product of prime powers in at most 29 * 8 multiplications. This trick also speeds up powers precalc in two times. Overall complexity of the solution assuming constant time for each 128bit operation is
You may also ask "Why did I annoy all by crappy 128bit arithmetic?". This is because I almost invented more elementary solution with O(2^{N/3}) precalc and poly(N) routine for each test. So I decided that staying under 64bit arithmetic could be dangerous. Actually I spent the whole day to code the working 128bit version having working 64bit version. So this annoyed me too :) ALTERNATIVE SOLUTION:@winger solution is very interesting and differs from described one. Solution by @mugurelionut is based on more elementary math than Granville formula. You can read about it here. AUTHOR'S AND TESTER'S SOLUTIONS:Author's solution can be found here. RELATED PROBLEMS:eolimp  322  Binomial Coefficients 5 The good problems to practice your skills on direct problems on calculating reduced factorials modulo prime powers:
This question is marked "community wiki".
asked 15 Apr '13, 16:24

1) Can you estimate the time complexity of the official solution ? (per test case, as a function of n) I am asking because at some point I had an O(n^3) per test case solution and was too slow (I mean O(n^3) 128bit operations). I had to come up with extra ideas in order to cut the time complexity down to O(n^2 * log(n)) per test case (note that I don't mean base 2 logarithm). Of course, the time complexity per test case is not all that matters  preprocessing should be counted, too (my solution had O(n^3) preprocessing). 2) During the contest (while searching the web in the hope of finding useful mathematics to use for solving the problem) I did come across the eolimp problem you mentioned (with n <= 40). I didn't know there was any editorial available and I noticed that Anton was the only one with an accepted solution at that problem on eolimp :) Still.. I though that Russian or Ukrainian competitors would have an advantage because of that problem.. it seems that I was wrong. 3) During the contest I did come across Granville's paper (among many other papers). But I was looking for simpler equations/formulas so I automatically skipped Theorem 2, which looked rather complicated to me (so I thought it wouldn't be useful) :) In the end, I used only elementary mathematics in my solution (and I had to prove everything myself from scratch, except for how to compute the modular multiplicative inverse of an odd number modulo 2^n). I think @scli used the property from Granville's paper (I browsed his solution earlier and I noticed a i * i  j * j somewhere : I didn't understand it then, but now it's starting to make sense) answered 15 Apr '13, 18:02
@mugurelionut Can you explain me what you actually did in your solution i am not able to get it
(15 Apr '13, 18:22)
@amitupadhyay: I will explain my solution a bit later, when I find some time. I can tell you now what the most important values that I computed were: 1) PowerSum(i,j) = the sum of 1^j + 2^j + 3^j + ... + (2^i)^j (i.e. the sum of all the numbers from 1 to 2^i, each at the j^th power) (i,j<=120) 2) SumOfSubsetProducts(i,j)=the sum of the products of the numbers of each jelement subset of the numbers 1,...,2^i, and 3) SPODD(i,j)=the sum of the products of the numbers of all the (2^i  j)element subsets of the odd numbers 1, 3, ..., 2^i  1.
(15 Apr '13, 19:36)
My old solution to eolimp problem deals with similar sums but I can't do better than O(2^(n/2)) precalc + O(n) for each test. It will be really interesting to see how this approach could be developed to get polynomial solution.
(15 Apr '13, 20:59)
@mugurelionut thanks for the reply :) I think I will figure it out now :)
(15 Apr '13, 21:52)

I will try to explain the main ideas in my solution for this problem. Actually, my solution is quite similar to the general idea described in the editorial  the major difference consists of the way I compute F2(X) = the product of all the odd numbers <= X. Let's consider the binary representation of X and let's traverse its bits from the most significant one to the least significant one. Thus, let's assume that X = 2^p(1) + 2^p(2) + ... + 2^p(q) (where p(1) > p(2) > ... > p(q)). The first bit is handled in a special manner. We want to compute the product of all the odd numbers 1 * 3 * ... * (2^p(1)  1). Actually, this value will be precomputed and I will denote it by SPODD(p(1),0) (I will explain later what SPODD(i,j) means). Let's assume now that we reached the bit p(r >= 2) and let's denote by Y = 2^p(1) + 2^p(2) + ... + 2^p(r1) (i.e. the sum of all the bits of X which are more significant than p(r)). We now want to compute the product of all the odd numbers in the range (Y + 1) ... (Y + 2^p(r)). If p(r) is 1 or 0 then the product consists of just one number: (Y+1). Otherwise (if p(r) >= 2) then the product will be (Y + 1) * (Y + 3) * ... * (Y + 2^p(r)  1) (there are 2^(p(r)1) odd numbers in the product). This product can be expressed as:
Now I can introduce the values SPODD(i,j) = the sum of all the products u(1) * ... * u(2^(i  1)  j), where {u(1), ..., u(2^(i  1)  j} goes over all the subsets of the odd numbers {1, 3, ..., 2^i  1} having 2^(i  1)  j elements. Thus, SPODD(i,j) means that we consider all the subsets of odd numbers < 2^i having 2^(i1)  j elements. Obviously, by the definition, SPODD(i,0) = 1 * 3 * ... * (2^i  1). Our sum of terms mentioned earlier (Y^0 * ... + Y^1 * ... + ...) can be expressed now as Y^0 * SPODD(p(r), 0) + Y^1 * SPODD(p(r), 1) + ... + Y^j * SPODD(p(r), j) + ... Let's notice now that we only ever need at most 120 terms from this sum, when computing it modulo 2^120. Note that Y is an even number. Thus, only the terms corresponding to Y^0, Y^1, ..., Y^119 may have a nonzero remainder when divided by 2^120 (all the other terms are 0 modulo 2^120). Actually, we can do even better. When we reached the bit p(r) (r>=2), Y is an even number which is a multiple of at least 2^(p(r) + 1) (because Y=2^p(1) + ... + 2^p(r1) and p(r1) > p(r)). Thus, only the terms corresponding to Y^0, Y^1, ..., Y^k may be nonzero (mod 2^120), where k = 119 / p(r1). When we add things up, we notice that, in the worst case, we will need around 119/119 + ... + 119/3 = O(n * log(n)) 120bit operations (n = 120) for computing F2(X) (I stopped at 119/3 because we only use this method for p(r)>=2 and, thus, p(r)+1>=3 ; for p(r)=1 or 0 I explained earlier that the result is easy to compute). Since we evaluate O(n) different F2(X) values per test case, this adds up to an O(n^2 * log(n)) time complexity per test case. For now I left out a very important part  how to precompute all the numbers SPODD(i,j) (i,j <= 120) in O(120^3) time. I will explain this at another time, as the explanation is more complicated than anything I wrote here. answered 18 Apr '13, 05:07
@mugurelionut thanks got it completely nw :)
(18 Apr '13, 06:33)

though I was not able to solve the problem with some analysis I found out some facts
@anton_lunyov correct me if I am wrong. I was unable to form a series or any generalised formula. but my analysis gave me above relations. May be they help in making the program
link
This answer is marked "community wiki".
answered 15 Apr '13, 17:47
I didn't check the patterns but unlikely this could lead to a complete solution.
(17 Apr '13, 13:58)
