[Cqoi2014]数三角形——组合数

全栈程序员-用户IM • 2022年4月20日上午11:40 • 未分类

大家好，又见面了，我是你们的朋友全栈君。

Description：

给定一个nxm的网格，请计算三点都在格点上的三角形共有多少个。下图为4×4的网格上的一个三角形。

注意三角形的三点不能共线。

Hint：

1<=m,n<=1000

Solution：

直接算三角形肯定算死。

所以，先考虑所有的可能三角形。再减去不合法的三点共线的情况。

所有三角形：C((n+1)*(m+1),3)

不合法的情况怎么处理？？

开始的想法：

1.找所有的两端在坐标轴上的直线，算出来整点数:gcd(x,y)+1；再算上下，左右的直线。

但是发现可能有的不合法直线不过边框的整点！！bug

2.考虑直线的方程：ax+by+c=0

a，b，c是常整数。并且都在1~n（m）的范围内。

相当于求x，y的非负整数解的个数。（exgcd）

但是待定系数n^4，枚举系数n^3都不行。bug

正解：

优化一下

发现找直线非常复杂。

如果我们找线段呢？并且保证线段的两端都在整点上？相当于把直线根据整点拆开了

(a,b)(c,d）的线段中间的整点有gcd(abs(c-a),abs(d-b))-1个方案。

枚举线段减去中间放点的方案，这样还是n^4

发现，许多的线段本质上是一致的，只是平移了。

所以，我们只需要枚举所有的(0,0)(x,y),就可以了、。

平移的方案就是（n+1-x）*(m+1-y)相当于画出了一个矩形。

对于不是在坐标轴上的点，我们还要乘2，相当于上下一个对称情况。

Code：

#include<cstdio>
#define LL long long
int gcd[1010][1010];
int n,m;
LL t,ans;
inline int getgcd(int a,int b)
{
    if (gcd[a][b])return gcd[a][b];
    if (!a)return gcd[a][b]=b;
    if (!b)return gcd[a][b]=a;
    return gcd[a][b]=getgcd(b,a%b);
}
inline void calc()
{
    for(int i=1;i<=m;i++)gcd[0][i]=i;
    for(int i=1;i<=n;i++)gcd[i][0]=i;
    for(int i=1;i<=n;i++)
      for(int j=1;j<=m;j++)
        getgcd(i,j);
}
int main()
{
    scanf("%d%d",&n,&m);
    calc();
    t=(n+1)*(m+1);
    ans=t*(t-1)*(t-2)/6;
    for (int i=0;i<=n;i++)
      for (int j=0;j<=m;j++)
        if (i||j)
        {
            if (!i||!j)ans-=(LL)(gcd[i][j]-1)*(n-i+1)*(m-j+1);
            else ans-=(LL)2*(gcd[i][j]-1)*(n-i+1)*(m-j+1);
        }
    printf("%lld",ans);
}