Can you please help in solving this question ATCoder ABC127 Task E - Cell Distance . I searched for editorial they all are Japanese and Google Translate is also not good enough 
Oh, another boring math problem. I’ll try to make it clear.
1 Like
First of all, it’s not hard to find that we can deform the formula.
\sum_{i=1}^{K-1}\sum_{j=i+1}^{K}(|x_i-x_j|+|y_i-y_j|) = \sum_{i=1}^{K-1}\sum_{j=i+1}^{K}(|x_i-x_j|) + \sum_{i=1}^{K-1}\sum_{j=i+1}^{K}(|y_i-y_j|)
So if we work out the first sum on the right side of the equation, then obviously we can also work out the second.
If we fix two positions x_{i1,j1} and x_{i_2,j_2} on the chessboard. In this case, there are C_{N*M-2}^{K-2} options.
In other words, |x_{i1,j1} - x_{i2,j2}| appears C_{N*M-2}^{K-2} times.
But enumerating all point pairs is undoubtedly get TLE, so we can enumerate d = |x_{i1,j1}-x_{i2,j2}|,d\in[1,K-1].
Let’s see how many (x_{i1,j1},x_{i2,j2}) is satisfied when d = 1.
Obviously there are M^2*(N-1) species.
Let’s climb step by step: 
When d = \alpha, there are \alpha * M^2 * (N-\alpha) species.
So for each d, its contribution to the answer is C_{N*M-2}^{K-2}*d*M^2*(N-d).
Then sum it.
ans = \sum_{d=1}^{K-1}C_{N*M-2}^{K-2}*d*M^2*(N-d) + \sum_{d=1}^{K-1}C_{N*M-2}^{K-2}*d*N^2*(M-d)
ans = \sum_{d=1}^{K-1}C_{N*M-2}^{K-2}*d*(M^2N+MN^2-(M^2+N^2)*d))
ans = C_{N*M-2}^{K-2}*(\frac{k(k-1)}{2}*(M^2N+MN^2)-\frac{k(k-1)(2k-1)}{6}*(M^2+N^2))
My hands are a little sore.
5 Likes