LA 3295 (计数 容斥原理) Counting Triangles

时间：2024-01-20 21:04:51

如果用容斥原理递推的办法，这道题确实和LA 3720 Highway很像。

看到大神们写的博客，什么乱搞啊，随便统计一下，这真的让小白很为难，于是我决定用比较严格的语言来写这篇题解。

整体思路很简单：m*n的方格，其格点是(m+1)*(n+1)的点阵，选三个点有C((m+1)*(n+1), 3)中情况，其中能构成三角形的不容易计算，所以计算它的反面：三个点不能构成三角形，即三点共线的情况。

三点共线的情况也可以再分为三类：

①三点在一条水平线上，共有m*C(n+1, 3)种情况。

②三点在一条竖直线上，共有n*C(m+1, 3)种情况。

③然后就是三点在斜线下的情况，由于是对称的，不妨先统计\左上到右下方向的直线，最后乘2即可。

首先是gcd(i, j) - 1的含义：这是起点为(0, 0)终点为(i, j)的所有三点共线的情况。

令dp(i, j)表示i*j大小的方格中 有一个点在右下角 的三点共线的情况，根据容斥原理有如下递推关系：

dp(i, j) = dp(i-1, j) + dp(i, j-1) - dp(i-1, j-1) + gcd(i, j) - 1

令sum(i, j)表示i*j大小的方格中\方向的三点共线情况，也可以类似地递推：

sum(i, j) = sum(i-1, j) + sum(i, j-1) - sum(i-1, j-1) + dp(i, j)

最终答案就是：C((m+1)*(n+1), 3) - m*C(n+1, 3) - n*C(m+1, 3) - sum(i, j) * 2

 #include <cstdio>

 typedef long long LL;

 const int maxn = ;

 LL dp[maxn + ][maxn + ], sum[maxn + ][maxn + ];

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

 LL C(LL n) { return (LL)n * (n-) /  * (n-) / ; }

 int main()

 {

     for(int i = ; i <= maxn; i++)

         for(int j = ; j <= maxn; j++)

             dp[i][j] = dp[i-][j] + dp[i][j-] - dp[i-][j-] + gcd(i, j) - ;

     for(int i = ; i <= maxn; i++)

         for(int j = ; j <= maxn; j++)

             sum[i][j] = dp[i][j] + sum[i][j-] + sum[i-][j] - sum[i-][j-];

     int n, m, kase = ;

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

     {

         n++; m++;

         printf("Case %d: %lld\n", ++kase, C(n*m) - C(n)*m - C(m)*n - sum[n-][m-] * );

     }

     return ;

 }

代码君

相关文章