Let hn(r)=n∑i=1ir.
hn(r),hm(r) can be computed for all 1≤r≤2k for both n,m in O(k2) using the recursion:
Let P_{ij} be the probability that (i, j) has a 1 in it after all the operations.
By linearity of expectation, we have to find \displaystyle \sum_{i, j} P_{i,j}.
Let p_{i,j} be the probability that cell (i, j) is flipped in one such operation.
The total number of submatrices is \dfrac{n(n+1)}{2} \dfrac{m(m+1)}{2}.
The number of submatrices containing (i, j) is i(n-i+1)j(m-j+1)
So,
Now, P_{i, j} = probability that this cell is flipped in odd number of operations:
So, we have to find:
Let t = - \dfrac{8}{n(n+1)m(m+1)}. Also, let f_n(i) = i (n + 1 - i) and expand using binomial theorem:
We have :
Now,
Hence, \displaystyle \sum_{i=1}^{n} f_n(i)^r can be computed in O(r) = O(k).
Thus the original formula can be computed in O(k^2)
We convert the problem into:
Given a value r, find the number of lines with distance \leq r from point q.
For this, consider a circle C with radius r centered at q. Consider two points A and B, both outside the circle C. The line passing through A and B has distance \leq r from q iff it intersects the circle C. Let F_A and G_A be the points of contacts of tangents drawn from A to the circle. Similarly define F_B and G_B.
We can prove that the line passing through points A and B intersects the circle C if and only if the line segments F_{A} G_{A} and F_{B}G_{B} do NOT intersect.
So, we need to draw 2 n tangents, and then draw n chords passing through the respective points of contacts, and count the number of intersections of these chords.
For this, sort the points by polar angles in O(n \log{n}) . Now we can count the number of intersections of line segments in O(n \log{n}), by iterating on the points.
Therefore, this question can be answered in O(n \log{n}).
Then we can just binary search to find the answer in complexity O(n \log{n} \log{\frac{R}{\epsilon}})