#P4558. [JLoi2016]方

    ID: 2023 传统题 1000ms 256MiB 尝试: 555 已通过: 193 难度: 8 上传者: 标签>CF2400提高+/省选-容斥原理贡献法组合枚举重复元素除重有序集合等差数列求和

[JLoi2016]方

题目描述

上帝说,不要圆,要方,于是便有了这道题。由于我们应该方,而且最好能够尽量方,所以上帝派我们来找正方形。

上帝把我们派到了一个有 nn 行 mm 列的方格图上,图上一共有 (n+1)×(m+1)(n+1) \times (m+1) 个格点,我们需要做的就是找出这些格点形成了多少个正方形(换句话说,正方形的四个顶点都是格点)。
但是这个问题对于我们来说太难了,因为点数太多了,所以上帝删掉了这 (n+1)×(m+1)(n+1) \times (m+1) 中的 kk 个点。
既然点变少了,问题也就变简单了,那么这个时候这些格点组成了多少个正方形呢?

输入格式

第一行三个整数 n,m,kn,m,k, 代表棋盘的行数、列数和不能选取的顶点个数。
接下来 kk 行,每行两个整数 x,yx,y,代表第 xx 行第 yy 列的格点被删掉了。

输出格式

仅一行一个正整数, 代表正方形个数对 100000007100000007(108+710^8 + 7) 取模之后的值。

2 2 4
1 0
1 2
0 1
2 1
1

数据规模与约定

对于 100%100\% 的数据,0≤x≤n≤1060 \le x \le n \le 10^6,0≤y≤m≤1060 \le y \le m \le 10^6,k≤2000k \leq 2000。

约定每行的格点从上到下依次用整数 00 到 nn 编号,每列的格点依次用 00 到 mm 编号。

保证 k≤(n+1)×(m+1)k \le (n + 1) \times (m + 1) 且不会出现重复的格点。