[CQOI2014]数三角形题解(组合数学+容斥)

[CQOI2014]数三角形题解(数论+容斥)

标签：题解
阅读体验：https://zybuluo.com/Junlier/note/1328780
链接题目地址：洛谷P3166 BZOJ 3505

思想还是很巧妙的。。。（~~对于我这种菜鸡~~）

理解题意

首先它说(n×m)的网格，实际上是有((n+1)×(m+1))个点来放三角形的顶点
然后就是算三角形的个数

怎么做

PS：以下所讲的所有(n)都是(n+1)，(m)也是

可以用(dbinom{n×m}{3})算出网格中选出三个点的方案数再容斥掉不是三角形的方案是吧
想一下什么情况下不是三角形：那肯定当且仅当三点共线时啊
那么怎么把三点共线的方案数算出来呢
分两种情况：

三点共线的直线平行于(x)或(y)轴：那很简单直接组合数减掉(dbinom{n}{3})和(dbinom{m}{3})
三点共线的直线是个斜的，这个有点困难啊。。。具体看下面

首先想一个(O(n^4))做法

考虑枚举三个点两端的两个点（为了不算重所以枚举两端的点）((x,y),(X,Y))
显然以这两个点为两端的共线方案数就是这条线中间经过的整点数是吧
我们会得到一个结论：方案数(=GCD(X-x,Y-y)-1)（画个图自己应该很好理解。。。）

怎么优化成(O(n^2))

我们发现其实很多直线其实长得是一样的对吧，只是放的位置不一样而已
我们考虑把这些长得一样的直线一起处理
那我们直接把((x,y))当做原点，枚举((X,Y))
会发现其实那些和他长得一样的直线相当于是在这种情况下于坐标网格中有限制地移动是吧
那么计算出它可以移动的方案数
这个很容易算，不就是网上移动不过((n-X))次，往右移动((m-Y))次嘛
那么具体算出来就是((n-X)*(m-Y))次了，再乘上(GCD(X,Y)-1)就是要减去的辣（当然只枚举了((X,Y))，斜率是正的，斜率是负的就只要反过来，于是我们(×2)）

可能有些不清楚，那么具体看代码实现

(code)

#include<bits/stdc++.h>
#define il inline
#define rg register
#define ldb double
#define lst long long
#define rgt register int
#define N
using namespace std;
const int Inf=1e9;
il int MAX(rgt x,rgt y){return x>y?x:y;}
il int MIN(rgt x,rgt y){return x<y?x:y;}
il int read()
{
    int s=0,m=0;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')m=1;ch=getchar();}
    while( isdigit(ch))s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
    return m?-s:s;
}

lst n,m,tot;
lst Ans;
lst GCD(rg lst x,rg lst y){return y?GCD(y,x%y):x;}

int main()
{
    
    n=read()+1,m=read()+1,tot=n*m;
    Ans=tot*(tot-1)*(tot-2)/6;
    Ans-=n*m*(m-1)*(m-2)/6+m*n*(n-1)*(n-2)/6;
    for(rg lst i=1;i<n;++i)
        for(rg lst j=1;j<m;++j)
            Ans-=2LL*(GCD(i,j)-1)*(n-i)*(m-j);
    return printf("%lld
",Ans),0;
}

[CQOI2014]数三角形 题解(组合数学+容斥)