AGC025D Choosing Points

Description

给定 $n, d_1, d_2$ ，请在 $2n\times 2n$ 的网格中找到 $n^2$ 个点，满足任意两点间的距离的平方既不为 $d_1$ 也不为 $d_2$ 。
注意网格的横纵坐标范围是 $[0,2n)$ 。
$1\leq n\leq 300,1\leq d_1,d_2\leq 2\times 10^5$

Solution

构造题带上距离什么的多半是从奇偶性方面去考虑..？比如说 $\text{Divide Points}$

奇偶性的本质还是对 $2$ 取模意义下的值。而对 $2$ 取模意义下的值做这道题，似乎并不好处理 $d_1$ 或者 $d_2$ 为偶数的值。不过这个思路启示我们从「模意义」的角度去思考这道题。

从「模意义」的角度来分析时，可以将值域简化到剩余系范围内，而代价是牺牲了部分情况之间的差异性。所以，既然取 $2$ 为模数无法看出不同的情况，我们考虑换个更大的模数来分析。

比如说 $4$ 。我们设 $d_1=c\times 4^k$ ，所以 $c\text{ mod } 4=1,2,3$ 。我们考虑一对点，假设它们的距离的平方恰好是 $d_1$ ，那么这对点的横纵坐标差一定都可以拆成 $a\times 2^k$ （注意：此处的 $k$ 与 $d_1$ 中的 $k$ 是同一个数）。我们假设横坐标差为 $a\times 2^k$ ，纵坐标差为 $b\times 2^k$ 。那么有下式：

$a^2+b^2 \equiv c\pmod{4}$

一个整数的平方在模 $4$ 意义下的值仅可能 $0,1$ 。 所以当 $c\equiv 3$ 时上式无论如何都不可能成立。我们只需要讨论 $c\equiv 1,2$ 的情况。

• $c\equiv 1$ 。此时 $a,b$ 中必定一奇数一偶数，也就是横纵坐标差的奇偶性不同。那么我们强制让选择的点的横纵坐标差的奇偶性相同即可。故此时我们根据 $a+b$ 的奇偶性来染色即可。
• $c\equiv 2$ 。此时 $a,b$ 必定两个奇数，也就是横坐标的差都是奇数。那么此时我们根据 $a$ 的奇偶性染色就可以了。

注意到上面我们只解决了 $d_1$ 的问题，并将所有的点分成了至多两类。事实上，我们用相同的方法考虑 $d_2$ ，那么至多将所有的点分成四类。而根据鸽巢原理 $4n^2$ 个点中选 $n^2$ 个点是一定可行的。

复杂度 $\mathcal{O}(n^2)$ 。

using namespace std;
int n, d1, d2, c1 = 1, c2 = 1;
int cnt[5];
inline int getcol(int x, int y){
    int ret = 0;
    if(d1 == 1) ret += ((x / c1 + y / c1) & 1) * 2;
    else ret += ((x / c1) & 1) * 2;
    if(d2 == 1) ret += ((x / c2 + y / c2) & 1);
    else ret += ((x / c2) & 1);
    return ret;
}
void solve(int col){
    int tot = 0;
    for(int i = 0; i < n + n; ++i)
    for(int j = 0; j < n + n; ++j)
        if(getcol(i, j) == col) {
            printf("%d %d\n", i, j);
            ++tot; if(tot == n * n) exit(0);
        }
}
int main(){

    fin >> n >> d1 >> d2;

    while(d1 % 4 == 0) d1 /= 4, c1 *= 2; d1 %= 4;
    while(d2 % 4 == 0) d2 /= 4, c2 *= 2; d2 %= 4;

    if(d1 == 3) d1 = 1;
    if(d2 == 3) d2 = 1;
    for(int i = 0; i < n + n; ++i)
    for(int j = 0; j < n + n; ++j)
        ++cnt[getcol(i, j)];
    for(int i = 0; i < 4; ++i)
        if(cnt[i] >= n * n) solve(i); 
    return 0;
}