2240. 「CQOI2014」数三角形

三倍经验

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!=mtimes (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-mfrac{n!}{(n-m)!}=n times (n-1) times (n-2) times dots times (n-m 1)。这不就是res times (n-m i)吗？如果觉得有问题，可以动脑想一想。

代码语言：javascript复制

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}^{ntimes 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）。

代码

我知道泥萌就想看这个：

代码语言：javascript复制

#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("%lldn",ans);
    return 0;
}

c++ ps

0 人点赞