首页 > 代码库 > UVA 12075 - Counting Triangles（容斥原理计数）

UVA 12075 - Counting Triangles（容斥原理计数）

2024-07-16 06:24:33   223人阅读

题目链接：12075 - Counting Triangles

题意：求n * m矩形内，最多能组成几个三角形
这题和UVA 1393类似，把总情况扣去三点共线情况，那么问题转化为求三点共线的情况，对于两点，求他们的gcd - 1，得到的就是他们之间有多少个点，那么情况数就能够求了，然后还是利用容斥原理去计数，然后累加出答案
代码：
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

const int N = 1005;
long long n, m, dp[N][N];
int cas;

long long gcd(long long a, long long b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}

void init() {
	cas = 0;
	for (int i = 2; i <= 1000; i++)
		for (int j = 2; j <= 1000; j++)
			dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + gcd(i, j) - 1;
	for (int i = 2; i <= 1000; i++)
		for (int j = 2; j <= 1000; j++)
			dp[i][j] += dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1];
}

long long C(long long n, long long m) {
	if (m > n) return 0;
	m = min(m, n - m);
	long long ans = 1;
	for (long long i = 0; i < m; i++)
		ans = ans * (n - i) / (i + 1);
	return ans;
}

int main() {
	init();
	while (~scanf("%lld%lld", &n, &m) && n || m) {
		n++; m++;
		printf("Case %d: %lld\n", ++cas, C(n * m, 3) - n * C(m, 3) - m * C(n, 3) - dp[n - 1][m - 1] * 2);
 	}
	return 0;
}


联系
我们