Kickstart 2017 Round A Problem A: Square Counting

Abridged problem statement

Count Number of ways to select four points in RxC grid such that these four points make  a square. These squares need not be aligned with the axes.

Constraints

1 ≤ T ≤ 100.

Small dataset

R, C < 10³

Large dataset

R,C < 10<sup>9

Print answer modulo 109 + 7</sup>

Approach  

Let us assume  C >= R.

First count all the squares that are aligned with the axes:             number of 1x1 squares is (R-1)*(C-1)
            number of 2x2 squares is (R-2)*(C-2)
            ...
            number of RxR squares is (R-R)*(C-R)

Now count all the squares not aligned with the axes:
         

We can see from the above image that a N x N square has N enclosing squares( including the green squares we counted in the previous step)

            number of squares in  1x1 grid is  1 * (R-1) * (C-1)
            number of squares in  2x2 grid is  2 * R-2)*(C-2)
            ...
            number of squares in  RxR grid is  R *(R-R)*(C-R)

Therefore total number of squares is ∑i=1Ri(R−i)(C−i)






which equals: ∑Ri=1RCi−Ri2−Ci2+i3

                                   = ∑Ri=1RCi−Ri2−Ci2+i3

                                   =  RC∑Ri=1i - (R+C)∑Ri=1i2 + ∑Ri=1i3

Code

#include <algorithm>
#include <iostream>

using namespace std;

const long long mod = 1e9 + 7ll;
const long long inv2 = mod / 2ll + 1;
const long long inv6 = 166666668ll;

long long sum1(long long x) {
  long long ans = x;
  ans = (ans * (x+1)) % mod;
  ans = (ans * inv2) % mod;
  return ans;
}
long long sum2(long long x) {
  long long ans = x;
  ans = (ans * (x+1)) % mod;
  ans = (ans * (2*x+1)) % mod;
  ans = (ans * inv6) % mod;
  return ans;
}
long long sum3(long long x) {
  long long ans = sum1(x);
  ans = (ans * ans) % mod;
  return ans;
}
int main(void) {
  //freopen("A.in", "r", stdin);
  //freopen("out.txt", "w", stdout);
  int testcase;
  cin >> testcase;

  for (int Case = 1 ; Case <= testcase ; ++Case) {
    long long r, c;
    cin >> r >> c;
    long long ans = 0;

    long long lim = min(r-1, c-1);
    ans = (ans + ((r * c) % mod) * sum1(lim)) % mod;
    ans = (ans - ((c + r) % mod) * sum2(lim)) % mod;
    ans = (ans + sum3(lim)) % mod;
    ans = (ans % mod + mod) % mod;
    cout << "Case #" << Case << ": " << ans << endl;
  }

  return 0;
}