2024.05.18 考试总结

附件：见 Problem.pdf 和 Solution.pdf.

T1： 构造一个简单无向图，使得号点与号点之间的最短路数量严格等于，且点数尽量少。

这道题其实就是一道很简单的思考题，其中给了，所以自然会联想到的处理方式，于是题目就变得简单了：

看这两张图，可见此时的路径数量为，其中表示分叉路的组数，这样，我们就能在只用个点的情况下（包括首尾）构造出一个的的路径条数，而我们有知道，对于每个数，一定可以拆分为的次幂的和的形式（例如、），所以我们可以再用大约个点来构造一条“外路”（原来的就称其为“内路”），如图所示：

如此构造有什么用处呢？不难发现，当我们需要构造条路径时，由于所以在已有的条路径上，我们可以这样连：

这样就轻易的构造出了一张条路径的图了，具体的方法是：若我们给每一列标一个号当需要条路径时，只需要将第列的“内路”和第列的外路连接就好了。注意，不用连的最多路径的（就是里面的），因为原来的图已经有那么多条路经了。

标号方式见图：

当时想这道题想了很久，后来才发现从一开始就少想了几种情况，导致耗费了大量的思考时间。

T3

这道题没有想到的是：的阶乘中有多少个可以用表示，再联系到，就知道该倒叙求值了。这里还有两个思维方式：1.由于的形式像极了的进制数，所以不妨设，用十进制来理解并推导式子，在推广到其他的；2.由于题目给了的条件，所以可以在求值的过程中直接模，结果并不会改变。