Atcoder abc127 Task e

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 :expressionless:

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: :smiling_imp:

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.:yum::yum::yum:

6 Likes

hey , @loopfree can u explain how for d=1 there are M^2*(N-1) species??