AcWing 98. 分形之城

题目链接：98. 分形之城 - AcWing题库

为了计算方便，我们把题目中房屋的编号都减去 $1$，即从 $0$ 开始编号，并把 $A$ 和 $B$ 也都减去 $1$。

本题的关键是要解决：求编号为 $M$ 的房屋（从 $0$ 开始编号）在 $N$ 级城市中的位置。

把该问题记为 $calc(N, M)$。

本题就是求 $calc(N, S)$ 与 $calc(N, D)$ 的距离。

不难看出，$N (N > 1)$ 级城市由四座 $N-1$ 级城市组成。

其中左上的 $N - 1$ 级城市顺时针旋转了 $90$ 度。

左下的 $N - 1$ 城市逆时针旋转了 $90$ 度。

进一步观察，当这四座 $N - 1$ 级城市首位相接后，左上、左下的 $N - 1$ 级城市的房屋编号顺序个字发生了颠倒。

这相当于左上、左下两座城市发生了 “水平翻转”。

在求解 $calc(N, M)$ 时：

因为 $N - 1$ 级城市有 $2^{2N - 2}$ 座房屋，

所以我们先递归求解 $calc(N - 1, M \mod 2^{2N - 2})$，

记求出的位置为 $(x, y)$，

其中 $x$ 为行号，$y$ 为列号，从 $0$ 开始编号。

再根据 $M / 2^{2N - 2}$ 的大小，很容易确定编号为 $M$ 的房屋处于四座 $N - 1$ 级城市中的哪一座。

1. 若处于左上的 $N - 1$ 级城市中：
   则需把 $(x, y)$ 所在的 $N - 1$ 级城市顺时针旋转 $90$ 度，
   坐标变为 $(y, 2^{N - 1} - x - 1)$，
   再水平翻转，
   坐标最终变为 $(y, x)$。

2. 若处于右上的 $N-1$ 级城市中：
   则该房屋在 $N$ 级城市中的位置应为 $(x, y + 2^{N - 1})$。

3. 若处于左下的 $N - 1$ 级城市中：
   则该房屋在 $N$ 级城市中的位置应为 $(x + 2^{N - 1}, y + 2^{N - 1})$。

4. 若处于左下的 $N - 1$ 级城市中：
   则需要把 $(x, y)$ 所在的 $N - 1$ 级城市你是整旋转 $90$ 度再水平翻转，
   坐标变为 $(2^{N - 1} - y - 1, 2^{N - 1} - x - 1)$。
   在 $N$ 级城市中的位置还要把行号再加 $2^{N - 1}$，
   最终得到 $(2^N - y - 1, 2^{N - 1} - x - 1)$。

pair<long long, long long> calc(int n, long long m) {
    if (n == 0) return make_pair(0, 0);

    long long len = 1ll << (n - 1);
    long long cnt = 1ll << (2 * n - 2);

    pair<long long, long long> pos = calc(n - 1, m % cnt);

    long long x = pos.first;
    long long y = pos.second;
    long long z = m / cnt;

    if (z == 0) return make_pair(y, x);
    if (z == 1) return make_pair(x, y + len);
    if (z == 2) return make_pair(x + len, y + len);
    if (z == 3) return make_pair(2 * len - y - 1, len - x - 1);
}

完整代码：分形之城