10233. 「一本通 6.6 练习 4」数三角形

2019-02-22 20:25:32


三倍经验

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) $吗? 如果觉得有问题,可以动脑想一想。 ```C++ 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$)。

代码

我知道泥萌就想看这个:

#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;
}