阿基里斯与乌龟谈消失的题面

· · 题解

前言

这是一篇实验性的题解,用于探讨对于特殊形式的题目，使用特殊形式的题解是否能 条理清晰且有趣地 讲明解题的思路与方式。

灵感来自于 《哥德尔、艾舍尔、巴赫书：集异璧之大成》 一书，题解中我也会模仿原文对话质朴的文风。

书中，作者侯世达多次采取了乌龟与阿基里斯对话的形式以使得讲述更加生动，因此我尝试套用这两个角色，写一篇题解给这道不甚传统的　“传统题”。

作为一篇拙劣的仿作，如果这篇博客因为学术性不足并不能通过题解审核，也是可以理解的，但我依然要尝试一下。

Sonata

（乌龟叩响了阿基里斯的房门。）

乌龟 ： 我亲爱的老朋友，你绝对想不到我带来的这个问题是多么绝妙！

阿基里斯 ： 我想以你与我的才智，这又会是再一次智力与思维的 奏鸣曲。 快把题面拿出来吧，龟兄。

乌龟 ： 真可惜，这道题没有题面——或者依题目自己的说法，题面已经 “丢失了”。

曾经，有一个题面摆在 ydc 的面前没有珍惜，直到失去时才后悔莫及，
如果上天再给他一次机会，ydc 一定会牢牢的记住这个题面。
没办法，已经失去了，所以这道题只能让你帮 ydc 做了。
已知的信息只有，这道题是传统题，采用全文比较的方式，时间限制 1s，空间限制 256MB。
ydc 还给你提供了这道题的所有数据。

乌龟 ： 阿基，这里就是题面了，让我们从分析题目数据开始吧。 但是在解题的时候，一定不要忘记这是一道 传统题。

Symphony

阿基里斯 ： 龟兄，这可是道传统题，直接用最简单的 打表 不就可以解决了吗？

乌龟 ： 只能说是你小瞧了我带来的这道题啊！源代码可是有 长度限制 的。 依我看，我们需要通过测试数据来猜测每个测试点要实现什么功能，然后用原来的方式实现。

阿基里斯 ： 龟兄，文件大小 真是这道题的关键，不如先把输入输出按照文件大小排序来看看吧。

乌龟（打开文件管理器） ： 我按你说的做。嗯…… #10 的输入输出文件都很小啊，让我把它打开……

(lost10.in)

Maybe this test case is the hardest, ever.
To get 100pts in this task, your program should pass the previous 9 test cases, and it should also be a "quine".
You can refer to http://en.wikipedia.org/wiki/Quine_(computing) for more information.

阿基里斯 ： 啊，是 Quine，这正是我了解的。这是一个以美国哲学家奎因命名的 自产生程序。我想这个测试点是要在最后完成的，我们可以用 这里的 方式把完成的源代码改造成一个 Quine。

乌龟（露出疑惑的神情） ： 阿基，虽然我不了解你说的什么 “奎因”，但你这就忘记了这是 传统题 吗，只需要把输出文件原样输出就可以了啊。

阿基里斯 ： 龟兄，不得不说这次是你占了先机啊，不过这么快拿到了 10 分，也是一件好事。

阿基里斯 ： 我想 #1，#2 和 #3 是比较类似的测试点，都是输入一个数字，输出一个二进制串……等等，#3 输出的是三进制，大同小异。

乌龟 ： 你说得对，阿基，但这三个串都长得我无从下手。

阿基里斯（托着下巴思考） ： 那么不如从长度开始吧，第一个串长度是多少？ 419304 ！ 这可是个不一般的数，我敏锐的数学直觉告诉我这是 2^{22}。

乌龟 ： 看到输入文件有 22，正常的人都能想到这个，我们需要更关键的性质。

阿基里斯 ： 等等，这个串似乎是回文的，再加上长度是 2^{22}，输入文件一定代表着对字符串操作的次数，而这个操作一定含有 每次翻倍。

乌龟 ： 突破性的进展！那么想必依照这种构造方式，0,1 出现的次数一定有迹可循。

很好，两种字符都出现了恰好 2097152 次，这个串一定是每次翻倍而构造的，我想，是取反后接在尾部，否则就 不能同时有两种字符了。

（乌龟和阿基里斯尝试着写出一段代码）

std::string s = "0";
std::string t;

inline void Generate() {
    t = "";
    repl(i,0,s.size())
        s[i] == '0' ? t += '1' : t += '0';
    s += t;
}

int main() {
    int n;
    scanf("%d",&n)
    for(int i = 1;i <= n;++i)
        Generate();
    std::cout << s << std::endl;
    return 0;
}

阿基里斯 ： #2 也先从长度入手吧，3524578，而输入是 33。龟兄，这个数恰好是斐波那契数列的第 33 位，F_{33} 啊。 而和斐波那契有关的字符串……

乌龟（点头回应） ： ……那便是斐波那契字符串！通过把字符串中 0 和 1 按照一定规则转化得到的串，我想，对于这个字符串便是每次变换把 0 变成 1 而把 1 变成 01 了。

std::string s = "0";
std::string t;

inline void Generate() {
    t = "";
    for(auto i : s)
        i == '0' ? t += '1' : t += "01";
    s = t;
}

int main() {
    int n;
    scanf("%d",&n);
    for(int i = 1;i <= n;++i)
        Generate();
    std::cout << s << std::endl;
    return 0;
}

乌龟 ： 然后这一阶段只剩第三个测试点了，让我看看长度…… 531452。阿基，你说这个数和输入数据 ： 12 有什么关系吗？

阿基里斯 ： 既然是三进制串，那自然会想到 3^{12}，但是 3^{12} = 531441，并不是 531452 但是很接近了。

乌龟 ： 好主意，阿基，这下显得有序多了。好像，这么划分后每个 $12$ 位的子串长度都是不一样的，让我们用文本编辑器搜索一下——果真如此！ 阿基里斯 ： 龟兄，不止如此，如果稍微对划分错位一下，还能划分出许多不同的 $12$ 位三进制串。 乌龟 ： 我不理解，为什么要打破已经分好的段落呢？ 阿基里斯 ： 你听我说，这些串都出现仅仅一次，你找不到任意的相同的 $12$ 位子串，说明这是包含了所有 $12$ 位三进制串的的一个字符串！ 让我们把这个串拆开，感受一下是怎么叠在一起的——快画个图吧 ： ![如果你看到这行字说明图片挂了](https://cdn.luogu.com.cn/upload/image_hosting/341mv0z3.png) 这让我想到一道题 ： [CF508D Tanya and Password](https://www.luogu.com.cn/problem/CF508D) 也是将许多串不重地拼接在一起，于是我们可以把这个问题放到图上。 乌龟 ： 稍等一下，图论……你的意思是把 **前面删除一位后面再添加一位的数之间连边**？ 阿基里斯 ： 是的，就是这样，这样我们就可以使用 **欧拉回路** 来求解这个问题了，和我提到的那道题十分相似。但是并不需要把图实际建立出来 ： ```cpp constexpr int N = 177147; std::string s = ""; int vis[N + 5]; std::stack<int> stk; inline void Generate(int x) { while(vis[x] < 3) { stk.push(3 * x + vis[x]); ++vis[x]; x = (3 * x + (vis[x] - 1)) % N; } } int main() { Generate(0); while(!stk.empty()) { int u = stk.top();stk.pop(); s += (char)(u % 3 + '0'); Generate(u / 3); } for(int i = 1;i <= 11;++i) s += '0'; std::reverse(s.begin(),s.end()); std::cout << s << std::endl; return 0; } ``` --- 乌龟 ： 阿基，我们真是进展神速，一鼓作气来看 \#4，\#5 和 \#6 吧，这三个数据点似乎是成组的。 阿基里斯 ： 妙极了，输入与输出都是先有一行一个整数 $n$，随后跟着 $n + 1$ 行，每行一个正整数。我想这是一系列 **$\mathbf{n}$ 次多项式**。我想我需要像拉马努金那样 “和所有的自然数做朋友” 才能猜到这三种变换了。 乌龟 ： 不过我认为这不是无迹可寻，起码可以先看看系数的关系。 - \#4 翻了一倍 - \#5 减半 - \#6 减少到 $\dfrac{1}{3}

而且 #4 和 #5 是互逆的操作。

阿基里斯 ： 我想，能恰好把系数翻倍和减半的只有平方和开根了，当务之急是找到模数。这里能找到最大的数是多少？

乌龟 ： 104688317。

阿基里斯 ： 我想，和这个数最接近的 NTT 模数便是 104857601 了，原根恰好为 3，我可要好好把多项式模板里的常量改好，免得套上了板子又变成对 998244353 取模，弄巧成拙。

乌龟 ： 那按你的说法，#6 就是多项式三次根了，这该怎么做？

阿基里斯 ： 我可是有办法的，甚至可以做多项式任意次数的开根。形象化地说，下面就叫开 k 次根吧。

对数函数可以把乘法变成加法，也可以把乘方变成乘法。那么用对数函数把开根变为乘法就可以了。

\ln \sqrt[k]{F(x)} &= \frac{F(x)}{k}\\ \sqrt[k]{F(x)} &\equiv \exp (k^{-1} \ln F(x)) \bmod x^n \end{aligned}

乌龟 ： 但是 F(x) 的第一项可不是 1，你要如何求多项式对数函数呢？

阿基里斯 ： 你问到关键了，我们先把每一项乘以第一项的逆元，最后每一项再乘以第一项单独开 k 次根的结果就行了，而求第一项的 k 次根，或者说 \mathbf{k} 次剩余。

x^k \equiv F(0) \pmod p

但是现在模数有一个原根 3，我们可以用 3^r 的形式表示一个数，现在式子化为 ：

3^{rk} \equiv F(0) \pmod p

那么这就是熟悉的高次同余方程的形式了，直接用 BSGS 求解就行。我可是对我的手写哈希表很有信心的。

不过似乎常数大了些？靠 O2 优化还是能通过的。

(阿基里斯拿出了他之前写的代码)

constexpr int SIZ = 100003;
struct HashTable {
    int tot;
    int head[SIZ];
    struct Node {
        int nxt,val;
        ll key;
    }p[N];

    HashTable() : tot(0) {mems(head,0);}

    inline int& operator [] (const int x) {
        int h = x % SIZ;
        for(int i = head[h];i;i = p[i].nxt)
            if(p[i].key == x) return p[i].val;
        p[++tot] = (Node) {head[h],0,x},head[h] = tot;
        return p[tot].val;
    }
}mp;

inline int BSGS(int a,int b) {
    const int mx = ceil(sqrtf(MOD));
    int base = b % MOD;
    rep(i,1,mx) {
        base = (ll)base * a % MOD;
        mp[base] = i;
    }
    base = qpow(a,mx);
    if(a == 0) return b == 0 ? 1 : -1;
    int prod = 1;
    rep(i,1,mx) {
        prod = (ll)prod * base % MOD;
        int px = mp[prod];
        if(px) return (((ll)i * mx - px) % MOD + MOD) % MOD;
    }
    return -1;
}

void exgcd(int a,int b,int& d,int& x,int& y) {
    if(!b) {
        d = a; x = 1; y = 0;
        return ;
    }
    exgcd(b,a % b,d,y,x);
    y -= x * (a / b);
}

int GetInv(int a,int p) {
    int d, x, y;
    exgcd(a, p, d, x, y);
    return d == 1 ? (x + p) % p : -1;
}

inline int gcd(int a,int b) {
    int k = __builtin_ctz(a | b);
    a >>= __builtin_ctz(a);
    b >>= __builtin_ctz(b);
    int p = a % b;
    while(p)
        a = b,b = p,p = a % b;
    return b << k;
}

inline void PolyResidue(const int *a,int *b,int n,int k) {
    static int x[N],c[N];int invk = qpow(k),invc = qpow(a[0]);
    repl(i,0,n) c[i] = (ll)a[i] * invc % MOD;
    PolyLn(c,x,n);
    repl(i,0,n) x[i] = (ll)x[i] * invk % MOD;
    PolyExp(x,b,n);
    int pw = BSGS(G,a[0]),w = INF;
    int M = MOD - 1,g = gcd(M,gcd(k,pw));
    k /= g,pw /= g,M /= g;
    int t = (ll)pw * GetInv(k,M) % M;
    for(;t < MOD - 1;t += M)
        w = std::min(w,qpow(3,t));
    repl(i,0,n) b[i] = (ll)b[i] * w % MOD;
}

乌龟 ： 我的朋友，我必须承认你在多项式这方面的造诣远超于我，但是在你一直思考多项式做法时忽略了一件事情，那就是这三组数据是特殊构造的。

仔细看看 #4 的输出，是回文的，而且第一项是 1，第二项就是 n，你想到了什么？是的，杨辉三角。我们靠一个简单的预处理阶乘和阶乘的逆元即可解决这个问题了，至于 #5 ，也就是把偶数位取反罢了。

而 #6，我确信它们也有差不多的特质。

阿基里斯 ： 龟兄，你是没能发现 #6 的特性吗，似乎确实如此，第一项并不是 1，那么唯一能和组合数靠上边的就是二项式定理了 ：

(a + b)^n = \sum_{k = 0}^{n} a^k b^{n - k} \binom{n}{k}

有了第一项和最后一项，再用上我上面的求 k 次剩余，求出 a,b 信手拈来！

不就是 a = 23333333,b = 33333333 吗。

乌龟 ：真是天才，说得让我想为你即兴创作一首赞美诗了，这样就有了常数更小的解法啦！

阿基里斯 ： 现在是时候来看最后三组测试点了，它们看起来也是颇为相似。首先一行三个数，然后是许多行，每行一个二元组或三元组。

乌龟 ： 这是常见的的图论的输入格式啊，我猜第一行三个数分别是点数边数和询问数，就记为 n,m,q 吧。

阿基里斯 ： 龟兄，#7 的输出只有 0 和 2139062143 或者说 0x7f7f7f7f，说明这组测试点的询问只有两种结果，我想不是询问路径长度奇偶性就是两点是否连通了。

乌龟 ： 让我写一个 并查集 验证一下……是的，是连通性，让我们看下一个数据点吧。

阿基里斯 ： n 个点 n - 1 条边，这可骗不过我，如果这个图连通，那么想必是一棵带边权的树。树上会有什么询问呢？

乌龟 ： 输入里没有输入树的根，那想必不是子树问题了，我觉得是树链询问吧，让我先把 树链剖分 写出来。嗯……输出的结果都不大，那应该是 树链 最大值，用 st 表就能实现 \mathcal{O} (n \log n) 预处理，\mathcal{O} (\log n) 查询了，比起线段树，我还是更喜欢 st 表。

阿基里斯 ： #9 的输入是带权图，询问似乎也是最值。啊，输出还有 0x7f7f7f7f，我猜是代表图上两点不连通。

那么应该就是把 [NOIP2013 提高组] 货车运输 反过来，改成求最小生成树然后求树上路径最大值，也就是图上两点之间最短路径中权值最大的。

乌龟 ： 我们已经解决了全部的测试点了，想必把代码组合在一起会像 交响乐 一样恢弘。

阿基里斯 ： 那我就把代码放在 这里 了。

乌龟 ： 辛苦你了，我的朋友。

Minuet

乌龟 ： 阿基，你知道吗，这种 “非传统的” 传统题可不止一道 ：

阿基里斯 ： 这可太有趣了，不过我们已经解决了这道题，是时候休息一会了，你有兴趣听一会优雅的 小步舞曲 吗？

乌龟 ： 再好不过了，我的朋友。