第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个包含三角函数的连续特徵值的连乘，一般人依然会陷入死胡同。

但齐物的大脑却在这一刻展现出了强大的代数降维能力。