「CQOI 2014」数三角形 题解

蒟蒻模拟赛题啥都不会

比赛时打了个 $O(n^2m^2)$ 的暴力还WA了

正题

题目要求在 $n \times m$ 个网格中选3个点组成三角型求方案数

然而 $n \times m$ 个网格中其实是有 $(n+1) \times (m+1)$ 个点的，所以下文中 $n$ 和 $m$ 都是加1之后的

我当时思路是枚举两个点然后计算第三个点的贡献，显然会T。考虑采用组合数和容斥解决： $\binom{n\cdot m}3$ 表示从所有点中选三个点，即所有“三角型”的数目。但实际上有很多不合法的情况，即三点共线的情况。其中三点共线的情况又分为竖着，横着，和斜着。

竖着和横着的情况较好处理（以横着为例）: 从横着总共 $m$ 个点中选3个: $\binom m3$，乘上总共 $n$ 行即： $n \times \binom m3$

最麻烦的是斜着的线

先考虑一个性质：斜着的两个点，设为 $A(a, b)$ 和 $B(c,d)$ ，之间的整点（不包括 $A$ 和 $B$ ）数有 $\gcd(|a-c|,|b-d|)-1$ 个。

可以这样理解： $\gcd(|a-c|,|b-d|)$ 即为 $A,B$ 两点间横坐标的差能被整分，同时纵坐标的差也能被整分的份数，再根据小学学过的植树原理，减去1就是 $A,B$ 两点间斜线段内的整点数.

然后，我们具体考虑怎样去除所有斜向不合法的点。如果一个一个点对去枚举的话同样是会超时的，必须优化。可以想到，斜率为正的线段和斜率为负的线段方案是一样的，于是可以只算正的最后把答案 $\times 2$ 。

还不够，继续优化，发现需要统计的线段中有很多斜率，长度一模一样的线段，只是位置不同，而计数问题显然不用考虑位置的影响，于是想办法高效计算这些一样的线段。我们可以只枚举线段的一个端点 $(x,y)$ ，把另一个端点固定为 $(0,0)$ ，这样就已经可以枚举出所有不同斜率和长度的线段了，这样的一条线段我们把它看作是选定端点再从内部选一个点组成的三角形，所以方案数为 $\gcd(|a-c|,|b-d|)-1$ 。然后考虑这样一个线段会出现多少次，是 $(n-x) \times (m-y)$ 次.

终于，得出结果是:

（枚举上界是 $n-1$ 和 $m-1$ （其实就是原题中的 $n,m$ ）的原因是我的点是从 $0 \sim n$ 编号的）

Talk is cheap, show me your code:

#include <cstdio>

typedef long long ll;
int n, m, tot;
ll ans;

int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen("testdata.in", "r", stdin);
  freopen("testdata.out", "w", stdout);
#endif
#ifndef LOCAL
  freopen("tri.in", "r", stdin);
  freopen("tri.out", "w", stdout);
#endif
#endif

  scanf("%d%d", &n, &m);
  ++n, ++m;
  tot = n * m;
  ans = 1ll * tot * (tot - 1) * (tot - 2) / 6 - 1ll * n * m * (m - 1) * (m - 2) / 6 -
        1ll * m * n * (n - 1) * (n - 2) / 6;
  for (int i = 1; i < n; ++i) {
    for (int j = 1; j < m; ++j) {
      ans -= 2ll * (gcd(i, j) - 1) * (n - i) * (m - j);
    }
  }
  printf("%lld", ans);
  return 0;
}