首页 > 代码库 > bzoj3505 数三角形 组合计数
bzoj3505 数三角形 组合计数
填坑……链接：http://www.lydsy.com/JudgeOnline/problem.php?id=3505
题意：给出一个矩形，任取三点，问不共线情况多少种。
首先我们利用补集转化，将这个问题转化为所有方案减去贡献情况。第一个显然是一个普通的组合数计算，关键在于后一半怎么计算。
看下面一个例子：
从$(0,0)$向$(2,4)$连了一条线，$gcd(2,4)=2$，然后这条线段中间有一个点。
实际上我们可以用函数解释。把这条线看做函数，我每走一个$(x/gcd(x,y),y/gcd(x,y))$都会经过一个整点，当我走到$(x,y)$时就走了$gcd(x,y)$个整点，再去掉终点就是结果。
然后，我们就可以寻找各种由同一直线平移或者旋转$180°$得到的直线，同时加上这些点的数量再计算即可。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 int n,m; 7 int gcd(int x,int y) 8 { 9 return (!y)?x:gcd(y,x%y); 10 } 11 int haha() 12 { 13 scanf("%d%d",&n,&m);long long cnt=(n+1)*(m+1); 14 long long num=cnt*(cnt-1)*(cnt-2)/6; 15 for(int i=0;i<=m;i++) 16 for(int j=0;j<=n;j++) 17 if(i||j) 18 { 19 long long t=1ll*(gcd(i,j)-1)*(m+1-i)*(n+1-j); 20 if(!i||!j)num-=t;else num-=2*t; 21 } 22 printf("%lld\n",num); 23 } 24 int sb=haha(); 25 int main(){;}
bzoj3505 数三角形 组合计数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。