CF1548D2 Gregor and the Odd Cows (Hard) 解题报告

解题报告

---

CF1548D2 Gregor and the Odd Cows (Hard)解题报告：

更好的阅读体验

题意

给定 $n$ 个点（保证没有三点共线），求选出三个点使得三角形面积为整数且内部整点数量为奇数的方案数。

$3\leqslant n\leqslant 6000$。（Easy Version：保证所有点的横纵坐标都是 $2$ 的倍数）

分析

我宣布计几就是个计几。

考虑 Pick 定理，设一个整点多边形面积为 $S$，内部格点数量为 $a$，边界格点数量为 $b$，那么有：

$$S=a+\frac{b}{2}-1$$

先考虑 Easy Version 的做法，由于所有点的横纵坐标都是偶数，根据三角形的某个面积公式：

$$S=\frac{x_1(y_2-y_3)+x_2(y_3-y_1)+x_3(y_1-y_2)}{2}$$

可以知道面积一定是偶数。那么 $\frac{b}{2}$ 也是偶数，即 $b$ 是 $4$ 的倍数。

我们发现一条边 $(x_1,y_1)(x_2,y_2)$ 经过的格点数量为 $\gcd(|x_1-x_2|,|y_1-y_2|)$ 所以我们需要的三个点需要满足它们三个值加起来是模 $4$ 为 $0$。

而根据 $\gcd(x,y)\bmod 4=\gcd(x\bmod 4,y\bmod 4)$，我们可以在模 $4$ 的剩余系下运算，那么就直接预处理 $cnt_{x,y}$ 表示横纵坐标模 $4$ 后是 $x,y$ 的整点数量，直接 $4^6$ 枚举每个位置模 $4$ 的值直接算就好了。

然后考虑 Hard Version 的解法。

此时的问题在于 $\frac{b}{2}$ 只需要为整数而不是偶数，也就是说 $b$ 有可能模 $4$ 余 $2$。

根据海伦公式（$S=\sqrt{p(p-a)(p-b)(p-c)}$，其中 $p=\frac{a+b+c}{2}$）可以发现面积为整数的三角形，三条边一定是三偶或者两奇一偶。第一种我们在每一个位置计数，第二种我们只在两个奇数边端点奇数，那么第一种是重复了 $6$ 次的，第二种只重复了 $2$ 次。（用手画画就差不多懂了）

发现 $n$ 很小，考虑固定三角形一个点 $p$，预处理 $cnt_{x,y,z}$ 表示横纵坐标模 $4$ 后分别为 $x,y$，且与 $p$ 的边上整点数量模 $4$ 为 $z$ 的点数。

类似 Easy Version，我们枚举与 $p$ 相连的两条边的所有信息（点的坐标以及整点数量模 $4$ 的余数），且点的横纵坐标奇偶性分别相同，整点数量奇偶性也相同（这里可以剪一下枝），于是我们可以计算出此时 $a$ 的值，只要 $a$ 为奇数，那么我们就按照枚举的边的奇偶性对答案分别进行贡献。

实现需要精细一点，时间复杂度：$O(n^2)$。

代码

Easy Version：

#include<stdio.h>
const int maxn=6005;
int n;
int x[maxn],y[maxn],cnt[4][4];
long long ans;
int gcd(int a,int b){
    return b==0? a:gcd(b,a%b);
}
int main(){
    scanf("%d",&n); 
    for(int i=1;i<=n;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        cnt[x%4][y%4]++;
    }
    for(int a=0;a<4;a++)
        for(int b=0;b<4;b++)
            for(int c=0;c<4;c++)
                for(int d=0;d<4;d++)
                    for(int e=0;e<4;e++)
                        for(int f=0;f<4;f++)
                            if((gcd(a-c,b-d)+gcd(a-e,b-f)+gcd(c-e,d-f))%4==0){
                                int x,y,z;
                                x=cnt[a][b],cnt[a][b]--,y=cnt[c][d],cnt[c][d]--,z=cnt[e][f];
                                ans+=1ll*x*y*z;
                                cnt[a][b]++,cnt[c][d]++;
                            }
    printf("%lld\n",ans/6ll);
    return 0;
}

Hard Version：

#include<stdio.h>
#include<math.h>
const int maxn=6005;
int n;
int x[maxn],y[maxn],cnt[4][4][4];
long long ans1,ans2;
int gcd(int a,int b){
    return b==0? a:gcd(b,a%b);
}
inline int calc(int a,int b,int c,int d,int e,int f){
    return (((a*(d-f)+c*(f-b)+e*(b-d))%4+4)%4);
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d%d",&x[i],&y[i]);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)
            if(i!=j)
                cnt[x[j]%4][y[j]%4][gcd(abs(x[i]-x[j]),abs(y[i]-y[j]))%4]++;
        for(int a=0;a<4;a++)
            for(int b=0;b<4;b++)
                for(int p=0;p<4;p++)
                    if(cnt[a][b][p]){
                        int rec=cnt[a][b][p];
                        cnt[a][b][p]--;
                        for(int c=a&1;c<4;c+=2)
                            for(int d=b&1;d<4;d+=2)
                                for(int q=p&1;q<4;q+=2)
                                    if(cnt[c][d][q]){
                                        int S=calc(x[i]%4,y[i]%4,a,b,c,d)/2,r=gcd(abs(a-c),abs(b-d));
                                        if((S-(p+q+r)/2+1)&1){
                                            if(p%2==0)
                                                ans1+=1ll*rec*cnt[c][d][q];
                                            else ans2+=1ll*rec*cnt[c][d][q];
                                        }
                                    }
                        cnt[a][b][p]++;
                    }
        for(int a=0;a<4;a++)
            for(int b=0;b<4;b++)
                for(int c=0;c<4;c++)
                    cnt[a][b][c]=0;
    }
    printf("%lld\n",ans1/6+ans2/2);
    return 0;
}