zoj 3647 – Gao the Grid

题意

这道题题意很简单,但是内涵却相当丰富,绝对是组合数学中的一大经典:

给出一个 n*m 的格子(格子是 n*m 个,交点是 (n+1)*(m+1) 个)

求,在这个格子里面以交点为顶点,能够形成多少个三角形?

粗略分析归约

脚趾头知道,这是一道组合数学题,而且离 DP 不远。

简单地归约一下,我们知道任取三点总共有 comb((n+1)*(m+1)) 种方式,我们要求的结果,只需要剔除掉所有直线的情况即可。

——其中 comb(m, n) 是组合数函数

那么,有多少种三点一线的情况?

DP 模型

我们假设对于 M*N 个顶点(M=m+1, N=n+1)的矩形,一共有 B[M][N] 这么多种“三点一线”的情况;

那么我们可以得到第一个递推:

等式一
B[i][j] = B[j][i] = B[i-1][j] * 2 - B[i-2][j] + A[i][j]

zoj-3647-1

如图解释一下上面的公式,我们要求 B[i][j],即三个点都在黑框 (ixj) 里的计数:

  1. 我们可以算出三个点都在红框里 ((i-1)xj) 里面的计数 B[i-1][j],加上篮框里面的计数 B[i-1][j]
  2. 根据集合与容斥原理,三个点都在黄色框里面的部分多算了一次,共 B[i-2][j] 个,要减回来;
  3. 这样算下来,还差了三个点既有在第一行,也有在最后一行的部分的计数(我们将其设为 A[i][j]),加起来就是 B[i][j],故得等式一

于是,我们就又将问题归约了,如何求 A[i][j]?首先我们定义一下 A[M][N],就是在 M*N 个顶点的点阵中任取三点,既有点在第一行,也有点在最后一行,并且三点共线的计数。

如何求 A[i][j],这貌似又是另一个 DP,不要紧,其实道理是一样的,我们再用一次容斥原理,得到第二个递推:

等式二
A[i][j] = A[i][j-1] * 2 - A[i][j-2] + f(i, j)

注意等式二与等式一的神似之处,道理是一样的,请自行脑补。那么我们就直接来说明 f(i, j) 的意义。

f(i, j) 就是在 i*j 的点阵中,任取三点,符合:

  1. 既有点在第一行,也有点在最后一行;
  2. 既有点在第一列,也有点在最后一列;
  3. 三点要共线;

根据前两点,可以断定这三点所形成的直线,就是这个点阵的对角线,而且其中两点是相对的顶点;

既然两点都已经定了,这个计数就等于第三个点(中间的点)有几个选择;

求法就是将对角线画出来,看看中间穿过有几个整数坐标点,那么 f(i, j) 就是几;

那这个怎么算呢?可以知道,(i*j) 的点阵相当于 ((i-1)*(j-1)) 的格子,那么不难求出,中间穿过的定点数就是 GCD(i-1, j-1)-1,其中 GCD 是最大公约数函数。

于是得到 f(i, j) 的表示:

等式三
f(i, j) = (GCD(i-1, j-1) - 1) * 2

注意要乘以二,因为对称地,对角线有两条。


至此递推式已经给出,然后我们再加上初始条件,给出 A[i][j]B[i][j] 的递推方程组:

A[0][j] = 0
A[1][j] = comb(j, 3) = j*(j-1)*(j-2)/6
A[i][j] = A[i][j-1] * 2 - A[i][j-2] + (gcd(i-1, j-1) - 1) * 2
B[0][j] = B[i][0] = B[1][j] = B[j][1] = 0
B[i][j] = B[j][i] = B[i-1][j] * 2 - B[i-2][j] + A[i][j]

如此,将 DP 矩阵 A 和 B 计算出来,然后对于输入的 m 和 n,结果就是:

B[M][N] = B[m+1][n+1]

这个是三点共线的计数,那么三角形的计数就是:

triangle(m, n) = comb(M*N, 3) - B[M][N] 
             = comb((m+1)*(n+1), 3) - B[m+1][n+1]

That’s all

发现由于很多解法都是用的蛮力或者半蛮力,我这个 DP 的解法稍为做了一下效率优化直接就排到了第三。


代码:

// 3854608  2015-01-23 20:22:10 Accepted    3647    C++ 50  11940   呆滞的慢板

#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long i64;
const int MAXN = 1002;

// 计算 C(k, 3) k 个点中取三个的组合数 
inline i64 ck3(i64 k) {
    return (k * (k-1) >> 1) * (k-2) / 3;
}

int gcd(int m, int n) {
    int r = 0;
    while(n) {
        r = m % n;
        m = n;
        n = r;
    }
    return m;
}

int A[MAXN][MAXN] = {};
i64 B[MAXN][MAXN] = {};
int CK3[MAXN] = {};

void init() {

    // 预处理计算组合数 
    for(int i = 0; i < MAXN; ++i) {
        CK3[i] = int(ck3(i));
    }
    // 计算 A 函数 DP 矩阵
    for(int i = 3; i < MAXN; ++i) {
        A[i][1] = i - 2;
    }
    for(int i = 1; i < MAXN; ++i) {
        for(int j = 2; j < MAXN; ++j) {
            A[i][j] = (A[i][j-1] << 1) - A[i][j-2] 
                    + (gcd(i-1, j-1)-1 << 1);
        }
    }
    // 计算 B 函数 DP 矩阵
    for(int i = 1; i < MAXN; ++i) {
        B[i][1] = B[1][i] = CK3[i];
    }
    for(int i = 2; i < MAXN; ++i) {
        for(int j = 2; j <= i; ++j) {
            B[i][j] = B[j][i] = B[i-1][j] * 2LL - B[i-2][j] + A[i][j];
        }
    }

}

int main() {

    init();

    int n, m;

    while(scanf("%d%d", &n, &m) != EOF) {

        n += 1;
        m += 1;

        printf("%lld\n", ck3(n*m) -B[m][n]);

    }

    return 0;

} 

【转载请附】愿以此功德,回向 >>

原文链接:https://www.huangwenchao.com.cn/2015/01/zoj-3647-gao-the-grid.html【zoj 3647 – Gao the Grid】

《zoj 3647 – Gao the Grid》有2个想法

  1. 您好, 我看到您在猪八戒的广告,以及您的技术方面的文章。想和您谈一个项目。 我们网站在加拿大。 是一个在线教育的网站,以金融计算机业界的应用内容为主,趋于本地化一些。 我们用的openEdx framework现在想请您有偿的重新设计一下网页的前端整体。 因为整个网页时python django 做的,前端改起来没有那么直接, 但我看您对这块比较 有研究, 希望可以合作。 我的email xlei1982@yahoo.ca 谢谢。

发表评论

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