单行道

无心人

此问题对每个N有个通用解 考虑从左到右，从下到上编号1 -- N^2 则左向连接1 到 N 再对之间除了1外每个点向上 下向连接上面的点直到遇到平方数点 上向连接1 到 N(N-1) + 1 再对之间除了1外每个点向右 右向连接右面的点直到遇到平方数点 然后相邻点如果没连接，则进行从大编号到小编号的方向的连接 这么得到的一个图乃很有规律的图

无心人

另外，每个点和相邻点的连接必然存在出和入两个方向，不能都出，不能都入

无心人

所以N=3时，考虑四个角和中心点 则可能数量是2^4 * 4 * 3 而不是2^9 对大的N也能得到小的组合数

shshsh_0510

呵呵， 无心人又开始争论了 在n较大时，那些边边角角的限制产生的影响就很小了。 主要的剪枝手段是除去各种对称变换下的同构。但是这个问题中比较明显的变幻好像只是转置，除数太小 另一个重要特征是顶点度小于等于4，但还不知如何利用

无心人

考虑f(N)为组合数 n = N $f(N) < 2^4 * 2^{4(N-3)} * 2^{4(N-2)} * f(N-2)$

mathe

大家可以同走格子线路统计问题比较一下看看，是否可以有类似的方法

gxqcn

现在提法有边缘“路口”的问题。试着改进一下，也不知是好是坏？ 假设四周路口新增“南北或北南”、“东西或西东”$2n$ 条直达单向隧道， （本想说“空中航线”的，但单向规定不合理） 即：有 $n xx n$ 个路口，之间有 $2n^2$ 条网状单行道联通， 要求从任意路口间至少存在一条路线到达另一个任意路口。请问共有多少种方案？ 如果是 $m xx n$ 个路口呢？（将有 $2 m n$ 条单行道） 新的提法，将使每个“路口”均正好与另外四个路口有联系而成为“相邻路口”。 再说明一下，这是我瞎编胡造的，只是出于对数学美的追求而已。

mathe

添加了以后,所有"路口"就都是十字路口了,比较美观一些 不过四面添加的4n条单向隧道定向对内部没有影响,它们的定向还是不要计算在里面.

mathe

弄明白了,gxqcn想要添加的是直接沟通东西和南北的2n条互不交叉的高架或地下隧道. 这样处理以后任何方向道路变成环路,这个就是另外一个比较有趣的题目了

gxqcn

我不知道改编后，难度是提升了还是下降了， 只是感到比较有趣。