题目描述

龙曲线（$\text{Dragon Curve}$）是一种著名的分形图案。本题定义了一个二进制字符串序列 {sn}\{s_n\}{sn​}，其中 $s_0=1$，并且递推关系为：

$$s_n=s_{n-1}1r(s_{n-1})$$

这里 $r(s)$ 表示将字符串 $s$ 反转后，再将所有 1 变为 0、所有 0 变为 1（即取反补码）。

机器人从原点出发，初始朝东，以每秒 $1$ 个单位的速度匀速运动，并在每运动 $1$ 秒后根据字符串 $s_{10}$ 的第 $k$ 个字符（$k$ 从 $1$ 开始计数）决定转弯方向：若该字符为 1 则左转 $90^{\circ }$，否则右转 $90^{\circ }$。已知当输入为 $s_{10}$ 时，机器人经过 $2^{10+1}=2048$ 秒后停在坐标 $(-32,32)$。

现在将输入字符串改为 $s_{30}$（初始条件相同），机器人将移动 $2^{31}$ 秒后停止。要求对于给定的任意时刻 $n$（$0\le n\le 2^{31}$），输出机器人从出发后经过 $n$ 秒时的坐标。

输入格式

输入包含多组测试数据。每组数据占一行，包含一个非负整数 $n$（$n\le 10^9$）。输入以负数（如 $-1$）作为结束标志。测试数据总数少于 $5000$ 组。

输出格式

对于每个输入的 $n$，输出一行，格式为 (x,y)，表示机器人经过 $n$ 秒后的坐标。

样例

输入

1
2
3
2048
1000000000
-1

输出

(1,0)
(1,1)
(0,1)
(-32,32)
(9648,-31504)

题目分析

本题的核心是计算由分形字符串 $s_{30}$ 所确定的路径上，前 $n$ 个移动单位的总位移。

直接模拟 $n$ 步是不可行的，因为 $n$ 可达 $10^9$，而 $s_{30}$ 的总长度是 $2^{31}$，远大于模拟上限。

观察递推式 $s_k=s_{k-1}1r(s_{k-1})$，可知字符串 $s_k$ 由三部分组成：

1. 前半部分：$s_{k-1}$，长度 $2^k$；
2. 中间一个字符 1，表示一次左转；
3. 后半部分：$r(s_{k-1})$，长度也是 $2^k$。

因此，整个路径也具有分形自相似结构：先走完 $s_{k-1}$ 对应的路径，然后左转 $90^{\circ }$，再走完 $r(s_{k-1})$ 对应的路径。关键在于，$r(s_{k-1})$ 所对应的路径与 $s_{k-1}$ 的路径之间存在确定的几何关系。

设 $p_k$ 为执行完整字符串 $s_k$ 后的位移向量，$d_k$ 为执行完后机器人的朝向向量（相对于初始方向）。由于机器人每次移动方向只能为东、北、西、南，我们可以用复平面上的单位向量表示方向。初始方向为东，即向量 $(1,0)$。左转相当于乘以虚数单位 $i$，右转相当于乘以 $-i$。

对于 $r(s_{k-1})$，它的路径是 $s_{k-1}$ 路径的“反向”版本：首先反转顺序，然后每个转向取反（左变右，右变左）。这个变换可以用向量运算描述。若已知 $p_{k-1}$ 和 $d_{k-1}$，则 $r(s_{k-1})$ 的位移 $q$ 和最终方向 $e$ 满足：

• 因为取反使所有转弯方向反转，所以最终方向 $e=-d_{k-1}$（相对于初始方向）；
• 位移 $q$ 满足 $q=(1,0)-d_{k-1}\cdot p_{k-1}+d_{k-1}^2$，其中 $d_{k-1}^2$ 表示方向向量旋转 $180^{\circ }$，即 $(-1,0)$ 方向的向量。

利用这些关系，我们可以递归地计算任意前缀的位移。

解题思路

向量表示与运算

用结构体 Vec 表示二维向量，重载加法、减法、乘法（复数乘法，用于旋转）。复数乘法规则：$(a+bi)(c+di)=(ac-bd)+(ad+bc)i$。在二维坐标中，向量 $(x,y)$ 对应复数 $x+yi$。

初始方向向量为 $(1,0)$，左转 $90^{\circ }$ 就是乘以 $(0,1)$，右转 $90^{\circ }$ 就是乘以 $(0,-1)$。

预计算完整字符串的信息

对于 $k=0$，有 $s_0=1$，即一个字符 1 表示左转。机器人先向前走 $1$ 秒（位移 $(1,0)$），然后左转，故 $p_0=(1,0)+(0,1)=(1,1)$，最终方向 $d_0=(0,1)$。

对于 $k\ge 1$，根据递推关系：

• 先执行 $s_{k-1}$，位移为 $p_{k-1}$，方向变为 $d_{k-1}$；
• 中间字符 1 使方向左转，得到方向 $d^{\prime }=d_{k-1}\cdot (0,1)$；
• 再执行 $r(s_{k-1})$，其位移相对于当前方向 $d^{\prime }$ 为 $q$（下面推导），最终方向为 $d^{\prime }\cdot e$，其中 $e=-d_{k-1}$。

计算 $q$：$r(s_{k-1})$ 的位移相对于执行 $s_{k-1}$ 的初始方向而言，可以表示为 $q=(1,0)-d_{k-1}\cdot p_{k-1}+d_{k-1}^2$。这里 $d_{k-1}^2$ 表示方向 $d_{k-1}$ 旋转 $180^{\circ }$ 后的向量。

推导思路：$r(s)$ 的路径等价于从原点出发，先沿 $s$ 的终点方向相反方向走一段，然后转向，最后到达一个位置。具体推导可借助复数几何，但本题解中直接使用上述公式。

因此，预计算数组 fullPos[k] 和 fullDir[k]，分别表示执行完整 $s_k$ 的位移和最终方向（均相对于初始方向）。递推时注意，后半部分的位移需要先乘以当前方向 $d^{\prime }$ 进行旋转，因为 $q$ 是相对于 $s_{k-1}$ 的初始方向的。

任意前缀的查询

对于给定的 $n$，我们要求 $s_{30}$ 前 $n$ 个字符对应的位移。定义一个递归函数 getPrefix(k, n, dir)，表示在初始方向为 dir 的情况下，执行 $s_k$ 的前 $n$ 个移动步（即前 $n$ 个字符）后的位移和最终方向。

递归过程：

• 若 $n=0$，返回零位移和 dir。
• 若 $k=0$，直接模拟两个字符（因为 $s_0$ 长度为 $2$，但 $n$ 可能为 $1$ 或 $2$）。
• 令 $half=2^k$（即 $s_{k-1}$ 的长度）。若 $n\le half$，则直接递归到 getPrefix(k-1, n, dir)。
• 否则，先走完 $s_{k-1}$，得到位移 $po{s}_1$ 和方向 $di{r}_1$；然后中间一个左转（因为字符是 1），方向变为 $di{r}_2=di{r}_1\cdot (0,1)$；剩余步数为 $n-half$，需要执行 $r(s_{k-1})$ 的前 $n-half$ 步。由于 $r(s_{k-1})$ 与 $s_{k-1}$ 结构类似但转向相反，我们定义另一个函数 getRevPrefix(k-1, r, dir) 来计算 $r(s_{k-1})$ 的前缀。

getRevPrefix 的递归逻辑类似，但是中间字符为右转，并且其前半部分仍是 $s_{k-1}$（因为 $r(s_{k-1})$ 的结构为 $r(s_{k-1})=r(s_{k-1})$？实际上，$r(s_k)=r(s_{k-1})0s_{k-1}$，因为 $r(ab)=r(b)r(a)$ 且取反交换。所以 $r(s_k)=r(s_{k-1})0s_{k-1}$。因此，$r(s_k)$ 的前半部分是 $r(s_{k-1})$，中间是 0（右转），后半部分是 $s_{k-1}$。这导致递归中，对于 $r(s_k)$ 的前缀，若 $n\le half$ 则调用 getRevPrefix(k-1, n, dir)，否则走完前半部分后中间右转，再调用 getPrefix(k-1, ...)。

通过这样的递归，每次 $k$ 减小 $1$，因此查询复杂度为 $O(30)$，完全可接受。

坐标变换与方向旋转

在递归过程中，每一步的位移都需要乘以当前的方向向量（因为位移是相对于当前方向的）。我们利用复数乘法实现旋转。

复杂度分析

• 预计算：$O(31)$ 次循环，每次常数运算。
• 每次查询：递归深度最多 $30$ 层，每层常数运算，因此 $O(1)$（常数约 $30$）。
• 总时间复杂度：$O(T\cdot 30)$，其中 $T\le 5000$，非常高效。
• 空间复杂度：$O(1)$（数组大小固定）。

代码实现

// Fractal
// UVa ID: 11253
// Verdict: Accepted
// Submission Date: 2026-06-21
// UVa Run Time: 0.000s
//
// 版权所有（C）2026，邱秋。metaphysis # yeah dot net

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

struct Vec {
    ll x, y;
};

Vec addVec(const Vec& a, const Vec& b) { return {a.x + b.x, a.y + b.y}; }
Vec subVec(const Vec& a, const Vec& b) { return {a.x - b.x, a.y - b.y}; }
Vec mulVec(const Vec& a, const Vec& b) { return {a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x}; }

Vec fullPos[31], fullDir[31]; // fullPos[k] = 完整 s_k 的位移，fullDir[k] = 最终方向

struct Result {
    Vec pos; // 位移
    Vec dir; // 最终方向
};

// 前向声明
Result getPrefix(int k, ll n, const Vec& dir);
Result getRevPrefix(int k, ll n, const Vec& dir);

// 计算 s_k 的前 n 步（移动段）
Result getPrefix(int k, ll n, const Vec& dir) {
    if (n == 0) return {{0, 0}, dir};
    if (k == 0) {
        Vec step1 = dir;
        Vec turn1 = mulVec(dir, {0, 1}); // 左转
        if (n == 1) return {step1, turn1};
        Vec step2 = turn1;
        Vec pos = addVec(step1, step2);
        return {pos, turn1};
    }
    ll half = 1LL << k; // s_{k-1} 的移动步数
    if (n <= half) return getPrefix(k - 1, n, dir);
    // 走完前半部分 s_{k-1}
    Vec pos1 = mulVec(dir, fullPos[k - 1]);
    Vec dir1 = mulVec(dir, fullDir[k - 1]);
    // 中间左转
    Vec dir2 = mulVec(dir1, {0, 1});
    ll r = n - half;
    Result part3 = getRevPrefix(k - 1, r, dir2); // 第三部分 r(s_{k-1})
    Vec totalPos = addVec(pos1, part3.pos);
    return {totalPos, part3.dir};
}

// 计算 r(s_k) 的前 n 步（移动段）
Result getRevPrefix(int k, ll n, const Vec& dir) {
    if (n == 0) return {{0, 0}, dir};
    if (k == 0) {
        Vec step1 = dir;
        Vec turn1 = mulVec(dir, {0, -1}); // 右转
        if (n == 1) return {step1, turn1};
        Vec step2 = turn1;
        Vec pos = addVec(step1, step2);
        return {pos, turn1};
    }
    ll half = 1LL << k;
    if (n <= half) return getPrefix(k - 1, n, dir); // 前半部分也是 s_{k-1}
    Vec pos1 = mulVec(dir, fullPos[k - 1]);
    Vec dir1 = mulVec(dir, fullDir[k - 1]);
    // 中间右转
    Vec dir2 = mulVec(dir1, {0, -1});
    ll r = n - half;
    Result part3 = getRevPrefix(k - 1, r, dir2); // 第三部分 r(s_{k-1})
    Vec totalPos = addVec(pos1, part3.pos);
    return {totalPos, part3.dir};
}

int main() {
    // 预计算完整 s_k 的位移和最终方向
    fullPos[0] = {1, 1};
    fullDir[0] = {0, 1};
    for (int k = 1; k <= 30; ++k) {
        Vec p = fullPos[k - 1], d = fullDir[k - 1];
        // r(s_{k-1}) 的完整位移 Q = 1 - d*p + d^2
        Vec q = subVec({1, 0}, mulVec(d, p));
        q = addVec(q, mulVec(d, d));
        // r(s_{k-1}) 的最终方向 R = -d
        Vec rDir = {-d.x, -d.y};
        // 左转
        Vec left = mulVec(d, {0, 1});
        fullPos[k] = addVec(p, mulVec(left, q));
        fullDir[k] = mulVec(left, rDir);
    }

    ll n;
    while (cin >> n && n >= 0) {
        Result ans = getPrefix(30, n, {1, 0});
        cout << "(" << ans.pos.x << "," << ans.pos.y << ")\n";
    }
    return 0;
}

总结

本题的关键在于识别龙曲线的分形递归结构，并利用向量运算（复数旋转）将路径的几何变换与字符串的递归定义紧密结合。通过预计算完整子串的位移和方向，以及对任意前缀进行分治递归，我们能够在常数时间内回答每次查询，从而高效解决大规模数据。

• 主要技巧：分形自相似性 + 向量旋转 + 递归降维。
• 注意点：$r(s)$ 的位移公式需要仔细推导，避免方向错误。
• 复杂度极低，适合处理 $10^9$ 级别的时间步长和多组测试数据。