Problem Link:Difficulty:Hard Prerequisites:Math, Combinatorics Problem:You are given N. Count how many NxN matrices are there, satisfying the following conditions: The constraint is: 3 <= N <= 10^7. Quick explanation:It seems that many users find the solution writing bruteforce for small values of N, searching for the corresponding sequence at OEIS, finding it here and using hint about fractional iteration of e^x  1, which leads to using higherorder Bell numbers as explained here. This approach leads to precalculation where The problemsetter was aware of presence on this sequence in OEIS while he creates the problem, but we decided that information provided there is not enough to solve the problem. Well we were wrong :( One of the purposes of this problem is to emphasize importance of minimizing the number of these heavy operations. The problemsetter solution described below use completely different approach and leads to a solution with only Explanation:The matrix you are supposed to find is very similar to a kind of distance function (condition (c) clearly implies triangle inequality). In fact, such a metric space (one that satisfies conditions (a)  (c)) is called an "ultrametric space". The spectrum of an ultrametric space X, denoted by Sp(X), is defined as the set of nonzero values that the distance can take. Note that, given a particular spectrum set S, we can transform it into an equivalent spectrum set {1, 2, ..., S}, just by keeping relative order. The question thus asks to find, given N, how many ultrametric spaces are there, having spectrum of size N2. We call the "diameter" of the space, denoted as diam(X), the largest distance between any two points in the space. Now, let us derive some useful properties of the ultrametric space. Also, we further denote M[x][y] as "d(x, y)" or "dist(x, y)". Intuitively, we would like to fill in values for dist(x, y) in a particular order. We could either start from 1 to diam(X), or we can go from diam(X) to 1. We end up choosing to fill in values from diam(X) to 1. Consider the relation R(d), (d > 0) on the set of points, where R(d)(x, y) iff dist(x, y) < d. This relation R(d) is an equivalence relation as can be verified: This further gives us, that if we were to fill in values for diam(X) in dist(x, y), we would have to partition the set of points X (this partition would define our equivalence classes for R(diam(X))), and then we'd get that all d(x, y) = diam(X) ACROSS such partitions! We also get from the above, that Sp(X) <= X  1. (You can prove this "directly" by considering relations R(d) : dist(x, y) < d, and letting d go from 1 to Sp(X)+1. Each time, R(i) merges atleast two equivalence classes of R(d1).) Clearly, for X = 1, this is true, since Sp(X) = phi. The important thing to keep in mind in the above is: Let f(N, K) = number of ultrametric spaces X, where X = N, and Sp(X) = k. Our ultimate goal is to find f(N, N2). Now, suppose we have our space X, and we need Sp(X) = X2. This can happen either due to We denote the answer to case (a) as A1, to case (b) as A2, to case (c) as A3. We can now deduce recurrences for A1, A2, A3, and one important term that would arise in all of them is f(N, N1) : [in A1, our spectra all have size Xi1. in A2, both spectra have such size. in A3, one spectrum has Xi1]. f(N, N1) can be thought of as: first partitioning the set X into two sets of size k and Nk, then dividing the set of Spectra from the union {1, 2, ..., N2} into parts of sizes k1, and Nk1 and then, by renumbering the spectra so that they are consecutive integers (1 to k1, or 1 to Nk1 respectively), we get the term corresponding to f(k, k1) and f(Nk, Nk1). That is, f(N, N1) = sum[Comb(N1, k1) * Comb(N2, k1) * f(k, k1) * f(Nk, Nk1), 1 <= k <= N1]. The first term corresponds to "the partition of size k containing a fixed element, say 1". The second term corresponds to dividing the set of distances {1, 2, ..., N2} into the part consisting of size k1, the rest going to the other part, and f(k, k1) and f(Nk, Nk1) correspond to the number of ways of getting ultrametric spaces satisfying the required conditions. Using induction, one can get that f(N, N1) = N! * (N1)! / 2^(N1). First fix two permutations, a permutation of the points from 1 to N (ppermutation), and a permutation of "distances between consecutive points" from 1 to N1 (dpermutation). That is, we visualize our pair (p, d) as follows:
Lets call this pair (p, d). We now map this permutationpair to an ultrametric space as follows: In other words, given this (p, d) pair, one can get the ultrametric space as: dist(x, y) is got by finding the largest value of the dpermutation that lies between the positions of x and y in the ppermutation. Now further, we get that we will be double counting because, at each point, we are dividing our set of points and distances into two parts, but the manner in which we do this does not depend on whether we have (left, right) or (right, left). Basically, for each value of d(i), we can swap the left and right parts of the permutations p and d, and still get the same ultrametric space. To illustrate this, consider N = 4, and the (p, d) pair as
The space that its mapped to will be the same as (by swapping about "d=3")
will be same as (by swapping about "d=1")
etc. Indeed, we will be double counting for each choice of d, whether to have it as leftright or rightleft permutations. This gives us our 2^(N1) in the denominator. Thus, f(N, N1) = N! * (N1)! / 2^(N1). Now, let us get back to calculating A1. This gives us, (similar to f(N, N1)): For this, one can compute this directly to arrive at the answer using rather robust calculation. The better way is to modify the above mapping with (p,d)pair. For distances < N2, they will partition it only into two parts, thus giving us a doublecount of 2 each. If we look at parts divided by N2, say
we can permute part1, part2, part3 arbitrarily among themselves, giving us a doublecount of 3!. Finally, since the two dpermutations
yield the same distances, after replacing N1 with N2, we get a doublecount of 2 from here. Putting it all together gives, For A2, we divide our set of points into sets of sizes k and Nk, choose k1 distances from {1, 2, ..., N3} for the first part, choose on these k1 distance as common distance of both parts and assign it and all other distances to the second part, and multiply the answer by the number of ultrametric subspaces for each part. This gives, This simplifies to N! * (N1)! / 2^(N1) * (N3)/6, which can be also derived from the (p,d)pair approach as follows. Let (p,d)pair be fixed. Choose some k from 1 to N3 and replace the value N1 with k, in the dpermutation. Then get your ultrametric space using the given mapping. For doublecounting, notice that in case A2, we need that the value N2 should be between k and N1 in the original dpermutation. Further, we have that
gives the same space as
Thus, we take just one out of the 3! possible ways of ordering k, N2, N1 in the dpermutation. This gives us a doublecount of 3!. Further, each time we divide our set into two parts, and this can be doublecounted twice in the leftright manner. Hence, we get A2 = (N3) * [N! * (N1)!/3!/2^(N1)]. Finally, we consider A3. Here, we pick one set of size k, and give it a spectrum of size k2, and give the remaining Nk elements a disjoint spectrum of size Nk1. Thus, Unfortunately, while we can still use our (p, d) permutationpair and replace N1 with k to give us a mapped ultrametric space, finding out how much we doublecount this is hard. Combining all three counted numbers together we get the final recurrence f(N,N2) = A1 + A2 + A3 = N! * (N1)! / 2^N * (N1)/3 + N! * (N3)! / 2^(N1) * Sum[2^k / k! / (k2)! * f(k,k2) : 3 <= k <= N1]. Putting g(N) = f(N,N2) / N! / (N1)! * 2^(N1) we get after straightforward calculations Using standard approach we can get rid of sum eliminating it using expression for g(N+1) and g(N): Multiply the first equation by N, and the second by (N2) and take difference, which will lead to: N * g(N+1)  (N2) * g(N) = N * N/6  (N1) * (N2)/6 + 2/(N1) * ((N1) * g(N)) This leads to This clearly leads to Finally we get Computing the value of F(N)Given this, let W(N) = N! * (2 + H(N)). Then, Also, F(N) = (1/2)^N * N! * (N!  2 * (W(N1)/3)). The easiest way is to precalculate pw2[], fact[] and W[] arrays completely, using However, we can exploit the fact that T is much smaller than maxN and do better. So as above we precalculate values of fact[] and W[] upto maxN, but values of pw2[n] only for n upto sqN := ceiling(sqrt(maxN)). Also we need values pw22[n] = 1/2^(sqN * n) for n upto sqN. Then for each N upto maxN we can represent it as N = sqN * u + v, with u = N / sqN and v = N % sqN and calculate 1/2^N as 1/2^(u * sqN + v) = (1/2^sqN)^u * 1/2^v = pw22[u] * pw2[v]. This leads only to You can find the second solution mentioned in Quick explanation here. Though it uses only The third mentions solution is here. It uses Setter's Solution:Can be found here Tester's Solution:Will be updated soon.
This question is marked "community wiki".
asked 17 Jun '13, 19:41

Actually one doesn't need to write bruteforce to find this sequence in OEIS. The tests from problem statement are enough. We know A=res[10]%MOD, hence res[10] are one of those numbers: A, A+MOD, A+2MOD, A+3MOD, .... With res[3],res[4] and res[10]+8*MOD OEIS returns our sequence. :D answered 18 Jun '13, 04:27

My solution(which got accepted on the first try, no need for optimization or anything, also not to brag but i was one of the first people who solved this) was: For a given n >= 3 the solution is as follows: 1.Generate a matrix s2[n][k], where s2 represents stirling numbers of the 2nd kind (which represent number of ways to partition a set of n elements into k nonempty subsets). You can do that using recursive formula s2[0][0] = 1 and s2[n][k] = k * s2[n  1][k] + s2[n  1][k  1] if memory serves well. 1b.Put s2[i][i] = 0, for every i (don't forget this step). 2.Raise that matrix to the power of n  2. 4.The answer for the given n is at s2[n][1] Now when you play around with this matrix for a while you'll notice that the only thing you really need to precalc all the values of n are the two rightmost diagonals, just under the main diagonal (due to how matrix exponantiation works). After you notice this you only need a little bit of math to help you get the recursive formula and that's it. Around O(5N) computations but 3N of those are simple additions. Also my solution passes without optimizing modular addition, ie simply writing (A + B) % mod, instead of A += B, if (A >= mod) A = mod. Reason i didn't optimize this is cause i just simply forgot about it and it passed the first time around so i didn't feel the need for it. My (very sloppy) solution is: http://www.codechef.com/viewsolution/2220050 answered 18 Jun '13, 20:38
2
Well, your timing is 0.65 seconds out of 0.666.
(18 Jun '13, 20:48)
Good thing you placed 0.666 as a time limit instead of 0.6 :D
(18 Jun '13, 20:56)
