LOJ #2240. 「CQOI2014」数三角形
BZOJ 3505: [Cqoi2014]数三角形
Luogu P3166 [CQOI2014]数三角形
(Luogu要大一些。。。)题意
给定一个$n \times m$的网格,请计算三点都在格点上的三角形共有多少个。下图为$4 \times 4$的网格上的一个三角形。注意三角形的三点不能共线。思路
由题意可知,其实就是让你求一个网格内有多少个不同的三角形。 First Of All,这个网格是从$(0,0)$到$(n,m)$的,出现了令人难受的$0$,于是我们可以在一开始把$n++,m++$范围就变成了$(1,1)$到$(n,m)$$\quad (n,m)$都已$+1$。 由于三角形是不可以三点共线的,所以我们可以求出不符合条件的三角形个数(三点共线)以及所有的三角形个数(包括不符合的与符合的)。 那么最终的答案=总方案数即所有的三角形个数(包括不符合的与符合的)-不符合条件的三角形个数(三点共线) 有了这个思路后就可以开始解决这道题了。 总方案数很简单,无非就是在一个$(n,m)$的网格中任意选取$3$个点,求方案数嘛!所以我们可以搬出组合数公式是指从$n$个不同元素中,任取$m(m≤n)$个元素并成一组,叫做从$n$个不同元素中取出$m$个元素的一个组合;从$n$个不同元素中取出$m(m≤n)$个元素的所有组合的个数,叫做$n$个不同元素中取出$m$个元素的组合数。用符号$C(m,n)$ 表示。相信你一定看(mei)懂(kan)了。 没关系,反正你只需要记住组合公式:
$$C_{n}^{m}=\frac{n!}{m!(n-m)!}$$ 那么组合数的C++怎么实现呢?
方法一:暴力?不介绍。
方法二:优化的暴力
首先感觉枚举两次虽然不会TLE,但是容易爆long long。然而我非常懒,所以就不想打高精。为了防止爆long long。这里给出某个大佬的做法: 首先你枚举一个$i$从$1$~$m$。那么看一看上面的组合公式,哪些量可以用$i$、$n$、$m$来表示? 首先$m!=m\times (m-1) \times (m-2) \times \dots \times 1$。然后惊人的发现,这不就是$res/i$吗? 然后看$\frac{n!}{(n-m)!}$。因为$n!=n \times (n-1) \times (n-2) \times(n-3) \times \dots \times 1$,$(n-m)!=(n-m) \times (n-m-1) \times \dots \times 1$。因为$n>n-m$,所以$\frac{n!}{(n-m)!}=n \times (n-1) \times (n-2) \times \dots \times (n-m+1)$。这不就是$res \times (n-m+i)$吗? 如果觉得有问题,可以动脑想一想。
1 2 3 4 5 6 |
long long C(long long a,long long b){ long long res=1; for(long long i=1;i<=b;i++) res=(res*(long long)(a-b+i))/i; return res; } |
接下来废话少说,返回到这道题上。 总方案数$=C_{3}^{n\times m}$。 接下来算一算不满足的方案数(三点共线)。 如果是一列的三点共线:方案数$=C_{3}^{n}\times m$ 如果是一行的三点共线:方案数$=C_{3}^{m}\times n$ 如果是斜着的三点共线。那么就要通过枚举来看一看有多少是不满足的(三点共线) PS:一条斜线从$(0,0)$到$(x,y)$有$gcd(x,y)-1$个整点。 于是乎,我们可以枚举$x$、$y$,因为起点不一定为$(0,0)$,所以,每次枚举就要将答案减去整点的个数$\times (n-i)\times(m-j )\times 2$(因为有两条对角线,所以乘$2$)。
代码
我知道泥萌就想看这个:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
#include<bits/stdc++.h> using namespace std; long long n,m,ans; long long gcd(long long x,long long y){ return y==0?x:gcd(y,x%y); } long long C(long long a,long long b){ long long res=1; for(long long i=1;i<=b;i++) res=(res*(long long)(a-b+i))/i; return res; } //C(n,m)=n!/(m!*(n-m)!) int main(){ scanf("%lld%lld",&n,&m); n++;m++; ans=C(n*m,3); ans-=C(n,3)*m; ans-=C(m,3)*n; for(long long i=2;i<=n-1;i++){ for(long long j=2;j<=m-1;j++){ long long Pt=gcd(i,j)-1; ans-=Pt*(n-i)*(m-j)*2; } } printf("%lld\n",ans); return 0; } |