【题解】CF1925F - Fractal Origami

题目链接

https://codeforces.com/contest/1925/problem/F

题目大意

将一个边长为 $1$ 的正方形按如图所示的方法进行 $N$ 次折叠（上图为 $N = 2$ 的情况），折叠之后展开。

展开后的折痕分为两种，一种是向内凹陷的折痕，总长度记为 $V$，另外一种是向外凸出的折痕，总长度记为 $M$。

可以证明 $\displaystyle\frac{M}{V} = A + B\sqrt{2}$，其中 $A,B$ 均为有理数。求 $B$ 对 $999\text{ }999\text{ }893$ 取模的结果。

数据范围

$1\le N \le 10^{9}$

解题思路

直接拿张纸来手动折几次，经过观察和推理不难发现下列性质：

所有凹陷的折痕全都是在奇数层产生的，所有凸出的折痕全都是在偶数层产生的。
第 $i$ 次折叠前纸片总共有 $2^{i - 1}$ 层，折叠时对每一层产生总长度为 $\displaystyle\frac{1}{(\sqrt{2})^{i}}$ 的折痕。

设奇数层的折痕总长度为 $4L_1$，偶数层的折痕总长度为 $4L_2$，根据以上性质能够得到： $$ \[\begin{aligned} L_{1} &= \frac{1}{\sqrt{2}} + \frac{1}{(\sqrt{2})^{2}}\times 2^{0} + \frac{1}{(\sqrt{2})^{3}}\times 2^{1} + \cdots + \frac{1}{(\sqrt{2})^{n}}\times 2^{n - 2} = (\sqrt{2})^{n} + (\sqrt{2})^{n - 1} - 1 \\ L_{2} &= \frac{1}{(\sqrt{2})^{2}}\times 2^{0} + \frac{1}{(\sqrt{2})^{3}}\times 2^{1} + \cdots + \frac{1}{(\sqrt{2})^{n}}\times 2^{n - 2} = (\sqrt{2})^{n} + (\sqrt{2})^{n - 1} - \sqrt{2}- 1 \\ \end{aligned}\]

$$ 我是直接暴力推 $\displaystyle\frac{L_{2}}{L_{1}}$ 算出来 $B$ 的，实际上不用那么麻烦。

实现一个 $a + b\sqrt{2}$ 的类，重载一下加减乘除运算即可，这样省下了推式子的时间，而且还不容易出错。

参考代码

https://codeforces.com/contest/1925/submission/244500846