上帝说，不要圆，要方，于是便有了这道题。

由于我们应该方，而且最好能够尽量方，所以上帝派我们来找正方形上帝把我们派到了一个有N行M列的方格图上，图上一共有(N+1)*(M+1)个格点，我们需要做的就是找出这些格点形成了多少个正方形（换句话说，正方形的四个顶点都是格点）。

但是这个问题对于我们来说太难了，因为点数太多了，所以上帝删掉了这(N+1)*(M+1)中的K个点。既然点变少了，问题也就变简单了，那么这个时候这些格点组成了多少个正方形呢？

第一行三个整数 N, M, K， 代表棋盘的行数、 列数和不能选取的顶点个数。 保证 N, M >= 1， K <=(N + 1) ×(M + 1)。

约定每行的格点从上到下依次用整数 0 到 N 编号，每列的格点依次用 0到 M 编号。

接下来 K 行，每行两个整数 x,y 代表第 x 行第 y 列的格点被删掉了。

保证 0 <=x <=N<=10^6, 0 <=y<=M<=10^6，K<=2*1000且不会出现重复的格点。

仅一行一个正整数， 代表正方形个数对 100000007（ 10^8 + 7） 取模之后的值

输入样例#1：
2 2 4
1 0
1 2
0 1
2 1
输出样例#1：
1

上帝说，不要抄代码，要搞懂。于是便有了这篇题解。

本题是一道考察组合数学的好题。
显然，一看到n,m的范围，我们就已经知道不能把棋盘构建出来，不然会爆空间，妥妥的$color{blue}MLE$。
那么如何得出最终答案呢？
我们将网格中没有删去的点称作好点，已经删去的点称作坏点。设四个顶点均为好点的正方形有$tot$个，四个顶点中至少有1个坏点的正方形有$B_1$个，四个顶点中至少有2个坏点的正方形有$B_2$个，四个顶点中至少有3个坏点的正方形有$B_3$个，四个顶点中恰有4个坏点的正方形有$B_4$个。根据组合数学中的容斥原理，四个顶点均为好点的正方形个数
$$ans=tot-B_1+B_2-B_3+B_4.$$ 那么接下来具体说下计算不同类型正方形个数的方法。
不失一般性，不妨设$n<=m.$

格点正方形按照放置的位置可以分为以下两类：

边平行或垂直于格线（横竖交叉的直线）的正方形。看起来方方正正。

在n*m的棋盘中，“方方正正”型正方形的边长只有可能为$1,2,3,…,n.$

对于边长为$l$的正方形（下图是一个例子），

只要定下来一个顶点以及这个顶点所处的位置（左上，右上，左下，右下），整个图形就能确定了。我们只需考虑其右下角顶点一共有多少种可能的位置即可求出边长为$l$的正方形的数量。

不难看出，其右下角顶点只有可能是上图棕色长方形内部的点，该长方形长为$m-l$，宽为$n-l$，一共有$(m-l+1)(n-l+1)$个格点可以选择。因为每个格点对应一个正方形，所以边长为$l$的正方形一共有$(m-l+1)(n-l+1)$个。

以此类推，在$n*m$棋盘中，四个顶点均为好点的“方方正正”的正方形共有$sumlimits_{l = 1}^n {left( {n - l + 1} right)left( {m - l + 1} right)}$个。

边既不平行，也不垂直于格线的正方形。看起来歪歪扭扭。
然而，不好看并不意味着不好算。通过观察，我们可以发现这类正方形全部可以被“方方正正”的正方形给包围在其内部，如图所示。

我们考察边长为$n$的包围圈，会发现内部包围住的正方形共有$(n-1)$个。
这里没有全部画出来所有情况，但剩下那一种很好脑补。
通过以上推导，我们就得到了“歪歪扭扭”型正方形的计算式:

在$n*m$棋盘中，四个顶点均为好点的“歪歪扭扭”的正方形共有$sumlimits_{l = 1}^n {left( {n - l + 1} right)left( {m - l + 1} right)left( {l - 1} right)}$个。

两类总数求和，化简得：四个顶点均为好点的正方形共有$sumlimits_{l = 1}^n {left( {n - l + 1} right)left( {m - l + 1} right)l}$个。

这个式子可以$O(n)$算出来。

还是利用“包围圈”的思想。
常言道，计数要做到不重不漏。
考察棋盘内任意坏点P，设其到棋盘上边界的距离为$d$，到棋盘下边界的距离为$u$，到棋盘左边界的距离为$l$，到棋盘右边界的距离为$r$。

那么至少包含P的“方方正正”的正方形共有$min(l,d)+min(l,u)+min(d,r)+min(u,r)$个。
那么“歪歪扭扭”的正方形怎么算呢？显然，它一定在四个部分中的某两个相邻部分。它的边长一定是某一个直角三角形的斜边。

设其直角边分别为$a$和$b$，只需枚举。
时间复杂度$O(k)$。

对于一个正方形，只要给出两个顶点，那么这两个顶点的连线只有可能作为正方形的边或正方形的对角线。分类讨论即可。

考虑“包围圈”即可。

这里有一个小结论：对于$(x_A,y_A),(x_B,y_B)$两个点，它们的连线能组成格点正方形的对角线，当且仅当$(x_A-y_A)+(x_B-y_B)$是偶数。
为啥呢？数学证明也不难，考场上自己画画图就知道了。这里不详细讲证明。

与顶点中至少有2个坏点的情况同理。计算2个坏点的情况时顺带判定一下另两个点是好是坏即可。
由于这样就考虑了顶点的顺序，而顶点是无序的，因此最后的结果需要除以$C_3^2$.

与顶点中至少有2个坏点的情况同理。计算2个坏点的情况时顺带判定一下另两个点是好是坏即可。
由于这样就考虑了顶点的顺序，而顶点是无序的，因此最后的结果需要除以$C_4^2$.

还是贴下代码。想必通过前面的讲解你应该理解了大部分内容。
毕竟截止到发稿时，全网没有比我讲的更详细的了。

用哈希表来维护点的信息，注意需要取模。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;

ll n,m,k,ans;
const ll p=1e8+7,base=233,mod=250007; 
const ll maxn=3000300;
ll x[maxn],y[maxn];
ll cnt1,cnt2,cnt3,cnt4;
struct  {
    ll tot;
    ll h[maxn],from[maxn],to[maxn],nxt[maxn];
    void add(ll x,ll y)
    {
        
        ll num=(x*base+y)%mod;
        from[++tot]=x;
        to[tot]=y;
        nxt[tot]=h[num];
        h[num]=tot;
        //简单的链表 
    }
    bool find(ll x,ll y)
    {
        ll num=(x*base+y)%mod;
        for(ll i=h[num];i;i=nxt[i])
        {
            if(from[i]==x && to[i]==y) return true;
        }
        return false;
    }
}h;
void calc(ll x,ll y,ll z)
{
    if (!x||!y||z<2) return;
    z=min(z,x+y);x=min(x,z-1);y=min(y,z-1);
    cnt1=((z-y)*y%p+(z-x+y-1)*(y-z+x)/2%p+cnt1)%p;
}
void check(ll x1,ll y1,ll x2,ll y2)
{
    if (x1<0||x1>n||y1<0||y1>m||x2<0||x2>n||y2<0||y2>m) return;
    ll tmp=h.find(x1,y1)+h.find(x2,y2);
    cnt2++;cnt3+=tmp;if (tmp==2) cnt4++;
}
void solve(ll x1,ll y1,ll x2,ll y2)
{
    check(x1-(y2-y1),y1+x2-x1,x2-(y2-y1),y2+x2-x1);
    check(x1-(y1-y2),y1+x1-x2,x2-(y1-y2),y2+x1-x2);
    if ((x1+x2+y1+y2)%2) return;
    check((x1+x2-y1+y2)/2,(y1+y2+x1-x2)/2,(x1+x2+y1-y2)/2,(y1+y2-x1+x2)/2);
}
int main()
{
    scanf("%lld%lld%lld",&n,&m,&k);
    for(ll i=1;i<=k;i++)
    {
        scanf("%lld%lld",&x[i],&y[i]);
        h.add(x[i],y[i]);
    }
    for(ll i=1;i<=min(n,m);i++)
    {
        ans=((i*(n-i+1)%p)*(m-i+1)%p+ans)%p;
    }
    for(ll i=1;i<=k;i++)
    {
        cnt1=(cnt1+min(x[i],y[i])+min(x[i],m-y[i])+min(n-x[i],y[i])+min(n-x[i],m-y[i]))%p;
        calc(x[i],n-x[i],y[i]);calc(x[i],n-x[i],m-y[i]);
        calc(y[i],m-y[i],x[i]);calc(y[i],m-y[i],n-x[i]);
    }
    for(ll i=1;i<k;i++)
        for(ll j=i+1;j<=k;j++)
            solve(x[i],y[i],x[j],y[j]);
    ans=(ans-cnt1+cnt2-cnt3/3+cnt4/6)%p+p;
    printf("%lldn",ans%p);
    return 0;
}