BZOJ 3505: [Cqoi2014]数三角形( 组合数 )

时间:2022-01-04 09:44:07

BZOJ 3505: [Cqoi2014]数三角形( 组合数 )

先n++, m++

显然答案就是C(3, n*m) - m*C(3, n) - n*C(3, m) - cnt. 表示在全部点中选出3个的方案减去不合法的, 同一行/列的不合法方案很好求, 对角线的不合法方案cnt比较麻烦.

枚举对角线(左下-右上), 即(0, 0)-(x, y), 我们发现这种情况有(n-y)*(m-x)*2(算上左上-右下的)种, 然后中间有gcd(x, y)-1个点(不合法), 乘起来就好了.

----------------------------------------------------------------------------------

#include<bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
const int maxn = 1009;
 
int n, m;
 
int gcd(int x, int y) {
return y ? gcd(y, x % y) : x;
 
ll T(int x) {
return ll(x) * (x - 1) * (x - 2) / 6;
}
 
int main() {
scanf("%d%d", &n, &m); n++; m++;
ll ans = T(n * m) - ll(m) * T(n) - ll(n) * T(m);
for(int x = 1; x < m; x++)
   for(int y = 1; y < n; y++) 
    ans -= (gcd(x, y) - 1) * (n - y) * (m - x) << 1;
printf("%lld\n", ans);
return 0;
}

----------------------------------------------------------------------------------

3505: [Cqoi2014]数三角形

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 771  Solved: 471
[Submit][Status][Discuss]

Description

给定一个nxm的网格,请计算三点都在格点上的三角形共有多少个。下图为4x4的网格上的一个三角形。

注意三角形的三点不能共线。

Input

输入一行,包含两个空格分隔的正整数m和n。

Output

输出一个正整数,为所求三角形数量。

Sample Input

2 2

Sample Output

76

数据范围
1<=m,n<=1000

HINT

Source