CF 166E 题解

题面

Tetrahedron

解题

记 $f_n$ 为答案，走 $n$ 步有 $3^n$ 种方案。

如果走 $n - 1$ 步时不在原顶点，那么第 $n$ 步有一种走法能走回原顶点。

转通项公式，得到 $f_n = 3^{n - 1} - f_{n - 1}$。

推导过程

使用数学归纳法。

首先，我们验证一下条件 $f_1$ 和 $f_2$：

$$f_1 = 3^{1 - 1} - f_{1 - 1} = 1 - f_0 = 1$$

$$f_2 = 3^{2 - 1} - f_{2 - 1} = 3 - f_1 = 2$$

设：对于任意 $k \geq 2\space(k \in \N)$，都有 $f_k = \frac{3^k + 3 \times (-1)^k}{4}$。

证明：对于 $k + 1$ 也成立：

$$\begin{aligned} f_{k + 1} & = 3^{k + 1 - 1} - f_{(k + 1) - 1} \\ & = 3^k - f_k \\ & = 3^k - \frac{3^k + 3 \times (-1)^k}{4} \quad & \text{根据假设} \\ & = \frac{4 \times 3^k - 3^k - 3 \times (-1)^k}{4} \\ & = \frac{3^k + 3 \times 3^k + 3 \times (-1)^{k + 1}}{4} \\ & = \frac{3^{k + 1} + 3 \times (-1)^{k + 1}}{4} \\ \end{aligned}$$

Q.E.D.

再加上一点求幂的优化即可。

代码

#include <cmath>
#include <cstdio>
using namespace std;
typedef unsigned long long ULL;

const int MOD = 1e9 + 7;

int main() {
  int n;
  scanf("%d", &n);
  ULL f1;      // 当前计算的 f
  ULL f2 = 1;  // 上一个 f，此处是边界
  ULL fp = 1;  // 用到的 3 的幂
  for (int i = 1; i <= n; ++i) {
    f1 = (fp - f2 + MOD) % MOD;  // fp 取模过，大小关系不确定
    f2 = f1;
    fp = 3 * fp % MOD;  // 不模会爆 unsigned long long，此处可证无副作用
  }
  printf("%llu", f1);
  return 0;
}