显然这样的交点只能在长边上产生。记$g(n)$为每次替换后原（较大的小）矩形长边上新增的交点总数，则有
$$f(n)=4f(n-1)+g(n)$$
$g(n)$可以这样的来分析：记$g'(n)$为每次替换后每个矩形中长边上不计四个角上的顶点时新增的交点总数。
则每次替换后每个矩形中上下两个小矩形的短边中各产生$4g'(n-2)$的交点（因为它们是前一次替换中更小矩形的长边），中间两个小矩形各自有一条长边，共产生$2g'(n-1)$的交点，这四个小矩形在长边上共有4个交点，最后，这些矩形两两粘合，因此有
$$g'(n)=\frac{2g'(n-1)+4g'(n-2)+4}{2}=g'(n-1)+2g'(n-2)+2,$$
同理有
$$g(n)=g'(n)-2.$$
以上都是线性递推式，由其特征方程的根可计算得
$$g(n)=\frac{(-1)^{n+1}+2^{n+2}}{3}-3,$$
从而
$$f(n)=\frac{(-1)^{n+1}-5\cdot2^{n+2}+6\cdot4^n}{15}+1.$$
再记$\varphi$为欧拉Totient函数，先计算$10^{18}$模$\varphi(\varphi(17^7))=\varphi(17^6\cdot 16)=17^5\cdot 8 \cdot 16$的值x，再计算$10^x$模$\varphi(17^7)$的值，用费马小定理即得结果$237696125$。
注：因使用sympy库计算15在模$ 17^7$乘法群中的逆，以下代码为Python 3。
注2：本题线性递推式的计算是我国高中竞赛内容，在《高等数学》A类课程中亦有涉及（线性常微分方程）。
import sympy
m=17**7
r=pow(10,(10**18)%(8*16*(17**5)),16*(17**6))
print(((6*pow(4,r,m)-5*pow(2,r+2,m)-1)*sympy.mod_inverse(15,m)+1)%m)
|
