题解 UVA12075 【Counting Triangles】

搜到的题解我一直读不懂…断断续续做了几天之后决定自己写一篇。

首先，有一个暴力的做法：先固定三角形最左最上方的点，然后依次枚举另外两个点，枚举时保证三点不共线。
这是一个 $O((nm)^3)$ 的做法。显然会 $TLE$ 。

尝试用组合计数的知识解决这个问题：用组合数算出选三个不同点的方案数 $X$ ，三点在同一行或同一列的方案数 $Y$ ，三点在同一斜线上的方案数 $Z$ 。答案就是 $X-Y-Z$ 。

后面的内容将会按照如图所示的坐标系来描述。请先尝试适应这种坐标系表示方法（横纵坐标的方向， $n,m$ 的意义）。（我知道图太丑）

注意 $n * m$ 只是格子的数量。可选的点一共有 $(n+1)(m+1)$ 个。

计算 $X$ :

显然 $X$ 是在 $(n+1)(m+1)$ 个元素中任选 $3$ 个的组合数，即 $C_{(n+1)(m+1)} ^ {3}.$

计算 $Y$ :

每行都有 $C_{n+1}^{3}$ 种方案在同一行共线，每列都有 $C_{m+1}^{3}$ 种方案在同一列共线。

因此 $Y=mC_{n+1}^{3}+nC_{m+1}^{3}.$

虽然今天不是愚人节(至少我写这个的时候不是)，但是在继续下去算 $Z$ 之前，我们再讨论另外一种直接计算 $X-Y$ 的方案。这是我第一次写这道题时用的计算方法。（其实把上面的 $X-Y$ 化简也能得到下面的结果，但我只是提供多一种思路吧…）

当然，如果你已经因为做这道题搞得头昏脑涨，然后再来看这篇题解，那就可以跳过这部分，先看如何算 $Z$ 。

受前面暴力做法的启发（但并不完全和它相同），我们可以发现 $X-Y$ 就等于 $\sum\limits_{i=1}^{m+1} \sum\limits_{j=1}^{n+1}Q(i,j).$ 其中 $Q(i,j)$ 表示以 $(i,j)$ 为最上最左的顶点，且三点不在同一行或者同一列共线（可能在同一条斜线上共线）的方案数。

为了方便叙述，我们在这里设 $m'=m+1,n'=n+1$ 。因此共有 $m'n'$ 个点可以作为三角形的顶点。

考虑如何计算 $Q(i,j)$ ，设 $P$ 的坐标为 $(i,j)$ ，另外两个点为 $P_1,P_2$ ，显然有这样几种情况：

1. $P_1$ 与 $P$ 在同一行上， $P_2$ 在它们的下方。如下图所示。红点为 $P$ , $P_1$ 可以在所有的绿点中选择（有 $n'-j$ 个）， $P_2$ 可以在所有的棕点中选择（有 $(m'-i)n'$ ）个。共有 $(n'-j)(m'-i)n'$ 种方案。

可能你会问，如果是 $P_2$ 与 $P$ 在同一行， $P_1$ 在它们的下面呢？需不需要把这个方案数乘以 $2$ ？

不需要。因为我们计算的是选点的方案数。这里的 $P_1$ 指代的是其中的一个点， $P_2$ 指代的是另外一个点。它们的方案数与排列无关。选择的顶点情况一样就应该被认作是同一种方法。

2. $P_1$ 在 $P$ 的正下方， $P_2$ 在 $P$ 的斜下方。

为什么 $P_2$ 不能与 $P$ 在同一行呢？因为这样会和第一种情况有重复。

这样 $P_1$ 有 $m'-i$ 种选法， $P_2$ 有 $(m'-i)(n'-1)$ 种选法。

共有 $(n'-1)(m'-i)^2$ 种选法

3. $P_1,P_2$ 都在 $P$ 斜下方。

$P1$ 有 $(m'-i)(n'-1)$ 种选法， $P_2$ 有 $(m-i)(n'-1)-1$ 种选法。

共有 $\frac{(m'-i)(n'-1)[(m-i)(n'-1)-1]}{2}$ 种选法。注意要除以 $2$ ，因为同一种搭配算了两次。

这就是 $Q(i,j)$ 的算法了。时间复杂度为 $O(nm)$ 。它很优秀，可惜极限情况下还是会 $TLE$ 。

在上面的讨论里，我们发现：

$Q(i,j)=n'(n'-j)(m'-i)+(n'-1)(m'-i)^2+\frac{1}{2}(m'-i)(n'-1)[(m'-i)(n'-1)-1].$

最后的答案就是：

$\begin{aligned} X-Y&=\sum\limits_{i=1}^{m'} \sum\limits_{j=1}^{n'}Q(i,j) \&=\sum\limits_{i=1}^{m'} \sum\limits_{j=1}^{n'}{n'(n'-j)(m'-i)+(n'-1)(m'-i)^2+\frac{1}{2}(m'-i)(n'-1)[(m'-i)(n'-1)-1] } \end{aligned}$

不急，我们一部分一部分搞定。

设 $V_1=\sum\limits_{i=1}^{m'} \sum\limits_{j=1}^{n'}n'(n'-j)(m'-i),$

$V_2=\sum\limits_{i=1}^{m'} \sum\limits_{j=1}^{n'}(n'-1)(m'-i)^2,$

$V_3=\sum\limits_{i=1}^{m'} \sum\limits_{j=1}^{n'} \frac{1}{2}(m'-i)(n'-1)[(m'-i)(n'-1)-1],$

则 $X-Y=V_1+V_2+V_3.$

先化简 $V_1$ :

$V_1$

$=\sum\limits_{i=1}^{m'} \sum\limits_{j=1}^{n'}n'(n'-j)(m'-i)$

$=\sum\limits_{i=1}^{m'}n'(m'-i)\sum\limits_{j=1}^{n'}(n'-j)$

$=\sum\limits_{i=1}^{m'}n'(m'-i)[1+2+3+…+n'-1]$

$=\sum\limits_{i=1}^{m'}n'(m'-i)[(1+n'-1)(n'-1)/2]$

$=\sum\limits_{i=1}^{m'}\frac{n'^2(n'-1)(m'-i)}{2}$

$= \frac{n'^2(n'-1)}{2}\sum\limits_{i=1}^{m'}{(m'-i)}$

$=\frac{n'^2(n'-1)}{2}[1+2+3+…+m'-1]$

$=\frac{n'^2(n'-1)}{2} * \frac{m'(m'-1)}{2}$

$=\frac{m'n'^2(n'-1)(m'-1)}{4}$

再化简 $V_2$ :

$\begin{aligned}V_2&= \sum\limits_{i=1}^{m'} \sum\limits_{j=1}^{n'}(n'-1)(m'-i)^2 \&= \sum\limits_{i=1}^{m'} n'(n'-1)(m'-i)^2 \&=n'(n'-1) \sum\limits_{i=1}^{m'}(m'-i)^2 \&=n'(n'-1)[0^2+1^2+2^2+…+(m'-1)^2]\end{aligned}$

根据平方和的求和公式： $\sum\limits_{k=0}^nk^2=\frac{n(n+1)(2n+1)}{6}$ ，有

$\begin{aligned}V_2&=n'(n'-1)\frac{m'(m'-1)(2m'-1)}{6} \&=\frac{n'(n'-1)m'(m'-1)(2m'-1)}{6}\end{aligned}$

最后化简 $V_3$ :

$V_3$

$= \sum\limits_{i=1}^{m'} \sum\limits_{j=1}^{n'} \frac{1}{2}(m'-i)(n'-1)[(m'-i)(n'-1)-1]$

$=\frac{n'}{2}\sum\limits_{i=1}^{m'}(m'-i)(n'-1)[(m'-i)(n'-1)-1]$

$=\frac{n'}{2}\sum\limits_{i=1}^{m'}[(m'-i)^2(n'-1)^2-(m'-i)(n'-1)]$

$=\frac{n'}{2}[(n'-1)^2\sum\limits_{i=1}^{m'}(m'-i)^2 -(n'-1)\sum\limits_{i=1}^{m'} (m'-i) ]$

$= \frac{n'}{2}{(n'-1)^2[0^2+1^2+2^2+…+(m-1)^2]-[(n'-1)(1+2+3+…+(m'-1)] }$

同样地，由平方和求和公式和等差数列求和公式：

$\begin{aligned} V_3&= \frac{n'}{2}[(n'-1)^2*\frac{m'(m'-1)(2m'-1)}{6}-(n'-1)\frac{m'(m'-1)}{2}]\&= \frac{n'm'(m'-1)(2m'-1)(n'-1)^2}{12}-\frac{m'(n'^2-n')(m'-1)}{4} \end{aligned}$

最后，我们就可以 $O(1)$ 计算出 $X-Y$ 了（注意最后一行是加号不是等号）：

$\begin{aligned} X-Y&=V_1+V_2+V_3\&=\frac{m'n'^2(n'-1)(m'-1)}{4}+\frac{n'(n'-1)m'(m'-1)(2m'-1)}{6}\&+ \frac{n'm'(m'-1)(2m'-1)(n'-1)^2}{12}-\frac{m'(n'^2-n')(m'-1)}{4}\end{aligned}$

然后其实已经没有必要再化简了。

好，无论以哪种方法，我们已经计算出来 $X-Y$ 了。

接下来计算 $Z$ 。

计算 $Z$ :

计算 $Z$ 是一件很麻烦的事情。我们可以计算出每条非水平非直线上的点数。如果这个点数为 $x$ ，那么在这条斜线上共线的方案数就是 $C_x^3.$ 现在的问题是，如何计算每条直线的 $C_x^ 3$ 。

为了方便叙述，我们还是设 $m'=m+1,n'=n+1$ 。所以共有 $m'n'$ 个点可以作为三角形的顶点。同时，我们先算左上—右下方向的斜线对答案的贡献。由对称性可知，右上—左下方向的斜线对答案的贡献和它是相同的。

引理

平面直角坐标系上的点 $P_1(x_1,y_2)$ 与 $P_2(x_2,y_2)$ 连线上的整数点共有 $gcd(x_2-x_1,y_2-y_1)+1$ 个。( $x_1\leqslant x_2,y_1\leqslant y_2$ )

证明（参考了这里）

设 $g=gcd(x_2-x_1,y_2-y_1),y'=\frac{y_2-y_1}{g},x'=\frac{x_2-x_1}{g}$ 。

已知 $P_1,P_2$ 连线上的点 $(x,y)$ 必定满足 $y=y_1+\frac{y_2-y_1}{x_2-x_1}(x-x_1).$

即 $y=y_1+\frac{y'g}{x'g}(x-x_1)=y_1+\frac{y'}{x'}(x-x_1).$

由 $gcd$ 的最大性可知， $gcd(y',x')=1$

（假设 $gcd(y',x')=t>1$ ，那么 $y_2-y_1=gy'=gt\frac{y'}{t}$ , $x_2-x_1=gx'=gt\frac{x'}{t}$ ,显然 $(x_2-x_1,y_2-y_1)$ 会有更大的公约数 $gt$ ，而不是 $g$ 。产生矛盾，所以假设不成立）

意即， $y',x'$ 互质， $x'\nmid y'$ ，所以 $\frac{y'}{x'}$ 不为整数。

要使得 $y=y_1+\frac{y'}{x'}(x-x_1)$ 为整数，首先要满足 $x$ 为 $[x1,x2]$ 内的整数，并且 $x' \mid (x-x_1)$ 。所以 $x-x_1$ 必须为 $x'$ 的整数倍。又因为 $x_2-x_1=x'g$ ，所以 $[x_1,x_2]$ 内有 $g+1$ 个整数 $x$ ，满足 $x' \mid x-x_1$ 。（这 $g+1$ 个整数 $x$ 分别是 $x_1,x_1+x',x_1+2x',…,x_2-x',x_2$ ，可以写成 $x=x_1+kg,k\in[0,g]$ 的形式）。

证毕。

从上面的引理可知，若以 $(x,y)$ 为右下端点：以 $(1,1)$ 为左上端点的线段上有 $gcd(x-1,y-1)+1$ 个整点，以 $(1,2)$ 为左上端点的线段上有 $gcd(x-1,y-2)+1$ 个整点，…，以 $(x',y')$ 为左上端点的线段上有 $gcd(x-x',y-y')+1$ 个端点。