题解 LA3295

题目大意 多组数据，每组数据给定两个整数 (n,m)，请求出 (n imes m) 的网格（((n+1) imes(m+1)) 的格点）上有多少个不同的三角形（不共线的三元点组）。

分析 这道题和 LA3720 那道数直线的题很像。我们用 (dp[i][j]) 表示 (i imes j) 的网格中的其中一个点是 ((0,0)) 的三点共线的个数，用 (ans[i][j]) 表示 (i imes j) 的网格中总的三点共线的个数，有

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

[ans[i][j]=ans[i-1][j]+ans[i][j-1]-ans[i-1][j-1]+dp[i][j] ]

第二个式子最后一项是因为点 ((i,j)) 在 (i imes j) 网格连出的三点共线个数等于点 ((0,0)) 在 (i imes j) 网格连出的三点共线个数（因为矩形是中心对称的）。

最终答案为 (C_{(n+1)(m+1)}^3-(n+1)C_{m+1}^3-(m+1)C_{n+1}^3-2cdot ans[n][m])。

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int maxn = 1005;
const int maxm = 1005;

ll n, m;
ll dp[maxn][maxm], ans[maxn][maxm];

void Init(int N, int M)
{
	for(int i = 1; i <= N; ++i)
		for(int j = 1; j <= M; ++j)
			dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + __gcd(i, j) - 1;
	
	for(int i = 1; i <= N; ++i)
		for(int j = 1; j <= M; ++j)
			ans[i][j] = ans[i - 1][j] + ans[i][j - 1] - ans[i - 1][j - 1] + dp[i][j];
}

ll C(int x, int y)
{
	if(x < y) return 0;
	
	ll res = 1;
	for(int i = 1; i <= y; ++i)
		res *= x, res /= i, --x;
	return res;
}

int main()
{
	Init(1000, 1000);
	
	int t = 0;
	while(~scanf("%lld%lld", &n, &m) && n && m) {
		++n, ++m;
		printf("Case %d: %lld
", ++t, C(n * m, 3) - n * C(m, 3) - m * C(n, 3) - 2 * ans[n - 1][m - 1]);
	}
}