￥## 题目链接 https://code.google.com/codejam/contest/8284486/dashboard
题意
给一个m⋅n的格点图，求这个格点图中正方形的数目。
思路
包括正正方形和斜正方形。
正正方形数目
我们用f(i)表示边长为i的正方形数目。
明显可知f(1)=mn，我们推一下f(2),f(3)...。
设如下格点图的长为m，宽为n（设m≥n）： 
首先我们选定左上角的边长为2的正方形。
我们水平向右平移，每次平移一个单位，可以平移m−2次，会产生m−1个2⋅2的正方形。我们将其向下平移，每次平移一个单位，可以平移n−2次，会产生n−1个2⋅2的正方形。于是我们可知f(2)=(m−1)(n−1)
同理可以推得f(3)=(m−2)(n−2), f(4)=(m−3)(n−3), f(n)=(m−(n−1))(n−(n−1))
所以我们正正方形的数目：
ans1=f(1)+f(2)+...+f(n)
=∑i=1n(m−(i−1))(n−(i−1))
=∑i=0n−1(m−i)(n−i)
= n(n+1)(3m−n+1)6
斜正方形数目
首先，假设我们已经有一个i⋅i的正正方形了，那么正正方形中的最大斜正方形（表示其不能再增大）有多少个呢？我们设g(i)为边长为i的正正方形数目包含的最大斜正方形数目。
假设i=2：g(i)=1 
假设i=3：g(i)=2 
其实观察可知：在边长为i⋅i的正正方形里面，最大斜正方形的数目g(i)=i−1（选定一条边，除去最两边的2个点，其他点都有最大斜正方形）。
那么，我们每个边长为i⋅i的正正方形里面都有g(i)个斜正方形，我们边长为i的正正方形有f(i)个，那么所有的斜正方形数目为：
ans2=f(1)g(1)+f(2)g(2)+...+f(n)g(n)
=∑i=1nf(i)g(i)
=∑i=0n−1f(i)g(i)
=∑i=0n−1(m−i)(n−i)(i−1)
=n(2m−n)(n+1)(n−1)12
所以我们最后的结果为：n(n+1)(3m−n+1)6+n(2m−n)(n+1)(n−1)12
代码
#include <bits/stdc++.h>using namespace std;inline int in() {int x; scanf("%d", &x); return x;}#define PR(x) {cout << #x << ' ' << x << endl;}#define LL long longconst LL mod = 1e9 + 7;LL power(LL a, LL n) { LL res = 1; while (n) { if (n & 1) res *= a, res %= mod; a *= a; a %= mod; n >>= 1; } return res % mod;}LL DIV(LL a, LL b) { LL t = power(b, mod - 2); return a * t % mod;}LL mul(LL a, LL b) { return a * b % mod;}inline LL add(LL a, LL b) { return a + b < mod ? a + b : a + b - mod;}int main() { int T = in(), kase = 1; while (T--) { LL m, n; cin >> m >> n; m--, n--; if (m < n) swap(m, n); LL v1 = mul(n, n + 1); LL v2 = (3 * m - n + 1) % mod; LL res1 = mul(v1, v2); res1 = DIV(res1, 6); LL v3 = (2 * m - n) % mod; v3 = mul(n, v3); LL v4 = mul(n + 1, n - 1); LL res2 = mul(v3, v4); res2 = DIV(res2, 12); LL ans = add(res1, res2); cout << "Case #" << kase++ << ": " << ans << endl; } return 0;}
