题解 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_1P在同一行上,P_2在它们的下方。如下图所示。红点为P, P_1可以在所有的绿点中选择(有n'-j个),P_2可以在所有的棕点中选择(有(m'-i)n')个。共有(n'-j)(m'-i)n'种方案。

可能你会问,如果是P_2P在同一行,P_1在它们的下面呢?需不需要把这个方案数乘以2

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

2.P_1P的正下方,P_2P的斜下方。

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

这样P_1m'-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个端点。

我们设f[x][y]表示大小为xy的点阵里,有多少组三点共线且包含了左上角(1,1)。为什么要这么算呢?因为只要能算出来xy大小的点阵包含了左上角的的三点共线组数,我们就能算出来包含了右下角、左下角、右上角的——由于对称性,它们的答案是一样的。

已知当前计算的三点包含了左上角[ 假设是(1,1)而不是(0,0) ] 。左上—右下走向的共线的三点里一定有一个在最右下方。我们以最右下方的这个点为分类标准,依次统计。这样就能不重不漏。

那么,确定了最左上方和最右下方的点,与这两个点构成三点共线的组数就可以由中间那个点唯一确定了。

若最右下方的点坐标为(x,y),它和(1,1)之间有gcd(x-1,y-1)+1-2个整点可以做“三点共线”中的第三点。因此以(x,y)为右下端点,对统计的贡献就是gcd(x-1,y-1)+1-2=gcd(x-1,y-1)-1.

因此有递推公式:f[x][y]=f[x-1][y]+f[x][y-1]-f[x-1][y-1]+gcd(x-1,y-1)-1.

上面仅仅统计了包含(1,1)这个点的左上—右下走向共线的三点数。如何由此得到整个问题的答案?

由对称性我们可以知道,f[x][y]还表示大小为xy的点阵中,以(x,y)最右下点的左上—右下走向的共线的三点数。如果有左上—右下走向的三点,它们最右下的点不同,说明这三点是不可能相同的。

也就是说,x\times y的点阵中,所有左上—右下走向的三点共线方案数为\sum f[i][j],其中i \in[1,x],j\in [1,y].

最后做一个前缀和s[x][y]=\sum\limits_{i=1}^x\sum\limits_{j=1}^{y}f[i][j].

终于可以得到Z=2\times s[n'][m']

然后回顾之前的内容,整个问题就解决了。

代码实现应该算简单,我就不放了。

祝AC.

留下评论

您的电子邮箱地址不会被公开。 必填项已用*标注