第73章 数学直觉vs无穷算力
经过第一题的初步“试探”，
所有人都已经看出来了，如果和ai拼算力，人类阵营毫无胜算。
但有时候，人类的数学直觉，是可以和ai的无穷算力比拼的。
为了验证这个结论，命题组给出的第二题依旧是ai擅长的海量枚举类题目。
problem 2：图论与组合
【题目：设g为一个具有n=100000个节点的4-正则循环图cn(1，2)。
即每个节点i均与其距离为1和2的节点相连。
请计算出该巨型环状分子结构包含多少棵完全不同的生成树。
请给出严密的代数化简过程，並將最终结果对998244353取模。】
题目一出，不仅是选手，就连评委席上没参与出题的数学大牛也变了脸色。
“求图的生成树个数，在代数图论中有一个放之四海皆准的解法——基尔霍夫矩阵树定理。
只需要列出该图的拉普拉斯矩阵，去掉一行一列后，再求主子式的行列式即可。
但是，这个网络有十万个节点……
这意味著，选手需要求解一个99999x99999阶的超级矩阵的行列式！
初步估算，该矩阵里的元素数量高达上百亿，人类別说手算了，就是光把它写在纸上，都需要写到下辈子吧！”
听到菲尔兹奖得主博切尔兹教授的点评，弹幕里的吃瓜群眾纷纷表示已经力竭了。
“滴滴滴……”
博切尔兹的话音一落，企鹅“圆宝”、openai的“gpt-4”、阿力的“九章”等七大ai大模型的指示灯，开始疯狂爆闪！
机房的冷却液系统发出低沉的嗡鸣。
对於ai来说，十万阶的带状稀疏矩阵算什么？
根本不算事。
构建矩阵、高斯消元、lu分解！
恐怖的o(n3)计算量，在海量gpu算力集群的並行冲洗下，不过就是弹指一挥间的事情。
仅仅18秒！
“叮！”
“叮！”
“叮！”
七大ai的屏幕几乎在同一时间亮起绿灯。
【最终答案：745281932（mod 998244353）】
仅仅十多秒，10000000000个元素的行列式计算完毕。
另一边的人类阵营，六位天才额头冒汗。
这道题根本不可能用基尔霍夫矩阵去硬算。
必须寻找捷径——
水木大学的赵子贤，专精计算数学，他立刻放弃了完整的十万节点，开始在草稿纸上疯狂计算n=3，4，5，6时的小规模情况。
“一定存在某种线性递推关係，只要找到前几项，就能解出特徵方程的根。”
他的笔尖在纸上划出残影，试图用有限的算力去寻找隱藏的斐波那契式递推数列。
燕大的韦东和普林斯顿的johnchen则同时闭上了眼睛，在大脑中构建拓扑结构的对称群。
一號舱里的齐物，则沉静地看著屏幕上那个完美的环状立体网络。
不慌不慌……
齐物思维纷飞：“算力……行列式……数学可不是体力活。”
他拿起电容笔，开始书写答案。
他已经就看穿了这个网络的本质：结构具有完美的循环对称性，这是一个標准的循环图。
既然是循环图，那它的拉普拉斯矩阵就是一个循环矩阵。
而在代数图论中，循环矩阵的特徵值天然不就是单位根的傅立叶变换係数？
哪里需要去求什么劳什子行列式？
齐物落笔有神，写下一行公式：
对於循环图cn(1，2)，其拉普拉斯矩阵的非零特徵值为：
λk=4-2cos(2πk/n)-2cos(4πk/n)，k=1，2，……n-1。
观赛的院士们心中一愣：“他跳过了矩阵构建？这是要直接用谱图理论写特徵值解析式？”
齐物继续解答：
生成树的个数t(g)等於所有非零特徵值的乘积除以n。
面对这100000个包含三角函数的连续特徵值的连乘，一般人依然会陷入死胡同。
但齐物的大脑却在这一刻展现出了强大的代数降维能力。
“令xk=cos(2πk/n)
利用二倍角公式：cos(2θ)=2cos2θ-1
將特徵值因式分解，可得
λk=4-2xk-2(2xk2-1)
=6-2xk-4x_k2
=-4(xk-1)(xk+3/2)”
“beautiful！”
田港院士和博切尔兹教授对视一眼，纷纷讚嘆，“把超越函数的连乘，转换成代数多项式的连乘？”
齐物的解答仍在继续：
“n(k=1→n-1)[z-cos(2πk/n)]=[tn(z)-1]/[2^(n-1)?(z-1)]”
將z=-3/2代入，经过简单的正负號合併，原本需要计算一百亿次的十万阶矩阵行列式，在齐物的笔下，瞬间坍缩成了一个乾净优美的纯代数形式：
t(g)=(2/5)?[tn(3/2)-1]
“嘶——”
“切比雪夫多项式根恆等式!”
“什么不等式？”
“把十万个节点的图论问题，转变成了一个求第一类切比雪夫不等式t100000(3/2)的问题。”
“可是这看起来还是很复杂啊，能手算出来吗？”
“感觉还是很难……”
齐物看了一眼倒计时，还剩10分30秒。
足够了。
“切比雪夫多项式满足线性递推关係……”
他喃喃自语，在平板上列出一个2x2的状態转移矩阵，隨后直接利用算法竞赛里常见的“矩阵快速冪”。
对於十万次方，快速冪只需要log?(100000)≈17次矩阵乘法即可！
也就是17次二阶矩阵的乘法和取模。
齐物笔走龙蛇，在草稿纸上飞快计算加减乘除和模998244353的运算。
11分20秒。
12分10秒。
12分50秒。
齐物在答题器上输入最后九个数字，按下回车。
“叮！”
【齐物作答完毕，用时13分01秒。】
【最终答案：745281932。】
和ai的一模一样。
“代数几何同构映射！”
博切尔兹讶声道，“这个齐物的数学直觉有点无敌啊，我看资料上写他只是一个高中生，amazing！”
一旁的田港院士点头道：“思路很妙，齐物其实是把十万个图论中的离散拓扑节点，强行拉升到了一个代数曲线的模空间上。”
张益唐教授笑道：“相比於齐物的方法，ai的確是有些丑陋了。”
“不知道这个齐物钟情於哪个大学？”
“如果不是亲眼所见，我绝不相信一个17岁的高中生能有这种数学直觉。”
“ai：我算了一百亿次。
齐物：我画了个代数曲线当衝动就直接钻过去了，哈哈。”
隨著齐物成功破局，其他几何人类天才同样展现出强大的实力。
第16分40秒，普林斯顿的john chen利用代数数论中的分圆域性质，殊途同归，成功提交答案。
第17分15秒，燕大韦东利用生成函数与形式冪级数展开，成功解出。
隨后，刘一凡、李明泽也赶在20分钟的红线前，满头大汗地敲下了正確答案。
只有水木大学的赵子贤还在与数据搏斗。
他找对了方向，成功推导出了那个线性递推方程，但在最后利用特徵根公式求解时，由於要在模998244353意义下进行二次剩余（即求平方根）的计算，他在手算tonelli-shanks算法时，一个微小的取模借位出现了致命的失误。
“滴——”
倒计时归零。
赵子贤的手僵在键盘上，屏幕上他最后敲入的答案“745281910”，距离正確答案仅仅谬之毫釐。
【赵子贤，计算错误，本轮淘汰。】
人类阵营，仅剩五人。
所有人都已经看出来了，如果和ai拼算力，人类阵营毫无胜算。
但有时候，人类的数学直觉，是可以和ai的无穷算力比拼的。
为了验证这个结论，命题组给出的第二题依旧是ai擅长的海量枚举类题目。
problem 2：图论与组合
【题目：设g为一个具有n=100000个节点的4-正则循环图cn(1，2)。
即每个节点i均与其距离为1和2的节点相连。
请计算出该巨型环状分子结构包含多少棵完全不同的生成树。
请给出严密的代数化简过程，並將最终结果对998244353取模。】
题目一出，不仅是选手，就连评委席上没参与出题的数学大牛也变了脸色。
“求图的生成树个数，在代数图论中有一个放之四海皆准的解法——基尔霍夫矩阵树定理。
只需要列出该图的拉普拉斯矩阵，去掉一行一列后，再求主子式的行列式即可。
但是，这个网络有十万个节点……
这意味著，选手需要求解一个99999x99999阶的超级矩阵的行列式！
初步估算，该矩阵里的元素数量高达上百亿，人类別说手算了，就是光把它写在纸上，都需要写到下辈子吧！”
听到菲尔兹奖得主博切尔兹教授的点评，弹幕里的吃瓜群眾纷纷表示已经力竭了。
“滴滴滴……”
博切尔兹的话音一落，企鹅“圆宝”、openai的“gpt-4”、阿力的“九章”等七大ai大模型的指示灯，开始疯狂爆闪！
机房的冷却液系统发出低沉的嗡鸣。
对於ai来说，十万阶的带状稀疏矩阵算什么？
根本不算事。
构建矩阵、高斯消元、lu分解！
恐怖的o(n3)计算量，在海量gpu算力集群的並行冲洗下，不过就是弹指一挥间的事情。
仅仅18秒！
“叮！”
“叮！”
“叮！”
七大ai的屏幕几乎在同一时间亮起绿灯。
【最终答案：745281932（mod 998244353）】
仅仅十多秒，10000000000个元素的行列式计算完毕。
另一边的人类阵营，六位天才额头冒汗。
这道题根本不可能用基尔霍夫矩阵去硬算。
必须寻找捷径——
水木大学的赵子贤，专精计算数学，他立刻放弃了完整的十万节点，开始在草稿纸上疯狂计算n=3，4，5，6时的小规模情况。
“一定存在某种线性递推关係，只要找到前几项，就能解出特徵方程的根。”
他的笔尖在纸上划出残影，试图用有限的算力去寻找隱藏的斐波那契式递推数列。
燕大的韦东和普林斯顿的johnchen则同时闭上了眼睛，在大脑中构建拓扑结构的对称群。
一號舱里的齐物，则沉静地看著屏幕上那个完美的环状立体网络。
不慌不慌……
齐物思维纷飞：“算力……行列式……数学可不是体力活。”
他拿起电容笔，开始书写答案。
他已经就看穿了这个网络的本质：结构具有完美的循环对称性，这是一个標准的循环图。
既然是循环图，那它的拉普拉斯矩阵就是一个循环矩阵。
而在代数图论中，循环矩阵的特徵值天然不就是单位根的傅立叶变换係数？
哪里需要去求什么劳什子行列式？
齐物落笔有神，写下一行公式：
对於循环图cn(1，2)，其拉普拉斯矩阵的非零特徵值为：
λk=4-2cos(2πk/n)-2cos(4πk/n)，k=1，2，……n-1。
观赛的院士们心中一愣：“他跳过了矩阵构建？这是要直接用谱图理论写特徵值解析式？”
齐物继续解答：
生成树的个数t(g)等於所有非零特徵值的乘积除以n。
面对这100000个包含三角函数的连续特徵值的连乘，一般人依然会陷入死胡同。
但齐物的大脑却在这一刻展现出了强大的代数降维能力。
“令xk=cos(2πk/n)
利用二倍角公式：cos(2θ)=2cos2θ-1
將特徵值因式分解，可得
λk=4-2xk-2(2xk2-1)
=6-2xk-4x_k2
=-4(xk-1)(xk+3/2)”
“beautiful！”
田港院士和博切尔兹教授对视一眼，纷纷讚嘆，“把超越函数的连乘，转换成代数多项式的连乘？”
齐物的解答仍在继续：
“n(k=1→n-1)[z-cos(2πk/n)]=[tn(z)-1]/[2^(n-1)?(z-1)]”
將z=-3/2代入，经过简单的正负號合併，原本需要计算一百亿次的十万阶矩阵行列式，在齐物的笔下，瞬间坍缩成了一个乾净优美的纯代数形式：
t(g)=(2/5)?[tn(3/2)-1]
“嘶——”
“切比雪夫多项式根恆等式!”
“什么不等式？”
“把十万个节点的图论问题，转变成了一个求第一类切比雪夫不等式t100000(3/2)的问题。”
“可是这看起来还是很复杂啊，能手算出来吗？”
“感觉还是很难……”
齐物看了一眼倒计时，还剩10分30秒。
足够了。
“切比雪夫多项式满足线性递推关係……”
他喃喃自语，在平板上列出一个2x2的状態转移矩阵，隨后直接利用算法竞赛里常见的“矩阵快速冪”。
对於十万次方，快速冪只需要log?(100000)≈17次矩阵乘法即可！
也就是17次二阶矩阵的乘法和取模。
齐物笔走龙蛇，在草稿纸上飞快计算加减乘除和模998244353的运算。
11分20秒。
12分10秒。
12分50秒。
齐物在答题器上输入最后九个数字，按下回车。
“叮！”
【齐物作答完毕，用时13分01秒。】
【最终答案：745281932。】
和ai的一模一样。
“代数几何同构映射！”
博切尔兹讶声道，“这个齐物的数学直觉有点无敌啊，我看资料上写他只是一个高中生，amazing！”
一旁的田港院士点头道：“思路很妙，齐物其实是把十万个图论中的离散拓扑节点，强行拉升到了一个代数曲线的模空间上。”
张益唐教授笑道：“相比於齐物的方法，ai的確是有些丑陋了。”
“不知道这个齐物钟情於哪个大学？”
“如果不是亲眼所见，我绝不相信一个17岁的高中生能有这种数学直觉。”
“ai：我算了一百亿次。
齐物：我画了个代数曲线当衝动就直接钻过去了，哈哈。”
隨著齐物成功破局，其他几何人类天才同样展现出强大的实力。
第16分40秒，普林斯顿的john chen利用代数数论中的分圆域性质，殊途同归，成功提交答案。
第17分15秒，燕大韦东利用生成函数与形式冪级数展开，成功解出。
隨后，刘一凡、李明泽也赶在20分钟的红线前，满头大汗地敲下了正確答案。
只有水木大学的赵子贤还在与数据搏斗。
他找对了方向，成功推导出了那个线性递推方程，但在最后利用特徵根公式求解时，由於要在模998244353意义下进行二次剩余（即求平方根）的计算，他在手算tonelli-shanks算法时，一个微小的取模借位出现了致命的失误。
“滴——”
倒计时归零。
赵子贤的手僵在键盘上，屏幕上他最后敲入的答案“745281910”，距离正確答案仅仅谬之毫釐。
【赵子贤，计算错误，本轮淘汰。】
人类阵营，仅剩五人。