首页 > 其他 > 详细

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

时间:2015-08-31 23:29:01      阅读:394      评论:0      收藏:0      [点我收藏+]

技术分享

先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

 

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

原文:http://www.cnblogs.com/JSZX11556/p/4774176.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!