神奇迷宫

将一个$m\times n$大小的网格中部分方格之间用墙隔开，使得从左上角的方格出发恰好只有一条路到达其它任意方格，从而形成一个$m\times n$的迷宫。

下图分别是一个$9\times 12$的迷宫和一个$15\times 20$的迷宫：

记$C(m,n)$是不同的$m\times n$大小的迷宫的数量。能通过旋转或翻相互转化的迷宫视作不同的迷宫。

可以验证$C(1,1)=1, C(2,2)=4, C(3,4)=2415$，以及$C(9,12)=2.5720\times 10^{46}$（已四舍五入至5位有效数字）。

求$C(100,500)$，用科学计数法表示，并应写多AeB的形式，表示$A\times 10^B$，其中A四舍五入至5位有效数字。

本题难度:

解答

本题涉及m\times n方格中的生成树，根据该页面的公式，结果是 $$\frac{4}{mn}\prod_{i=1}^{m-1}\prod_{j=1}^{n-1}(\sin^2\frac{i\pi}{2m}+\sin^2\frac{j\pi}{2n})$$ 取$m=100,n=500$代入即得结果$6.3202e25093$。

注：为便于格式化输出，以下代码为Python 3。

from math import pi,sin,log10

m,n=100,500

x=sum(log10(4*(s1+s2)) for i in range(m) for j in range(n) if ((s1:=sin(i*pi/(2*m))**2)+(s2:=sin(j*pi/(2*n))**2))>0)-log10(m*n)
d=int(x)

print(f"{10**(x-d):.4f}e{d}")