Problem

一个正四面体顶点为$A,B,C,D$,从$D$出发,每走一步,更变当前所在顶点(不能保持不变),给定一个数$n$,求能有几种不同路径使得第$n$步走到$ D$。$1 \leq n \leq 10^7$

Solution

Method 1

当然是考虑递推辣
分两种情况:

  1. 第$ n-2 $步不在$ D$
  2. 第$ n-2 $步在$ D$

设$ a[n] $是第$ n $步到达$ D$的不同路径数。
对于 1 情况:第$ n-2 $步在$A,B,C$当中的一点,那么这时,在第$ n-1 $步能够到达$ D$,但其实他可以选择在第$ n-1 $到达另外两点,然后在第$ n $步到达$ D$,所以这种情况有$ 2a[n-1] $种。
对于 2 情况:第$ n-2 $步在$ D$点,那么他可以通过走到$A,B,C$中的任意一点,再回到$D$点,所以这种情况有$ 3a[n-2] $种。
故有$a[n]=2a[n-1]+3a[n-2]$

Method 2

特征方程!
优化至$O (\log n)$
Code:


通项公式:$a _ { n } = \frac { 3 } { 4 } \left( 3 ^ { n – 1 } – ( – 1 ) ^ { n – 1 } \right) ( n > 1 )$

Method 3

用$ dp[i][j] $表示第$ i $步走到$ j $点,则有:
$$dp[i][j]=dp[i][j]+dp[i-1][k]~~(j\ne{k})$$
于是从遍历$i,j,k$,最后取$ dp[n][3] $即可

Method 4

走$ n $步的总共不同路径有$3^{n}$条,若算出第$ n $点到达$ D $的概率,最后乘上$3^{n}$再取模即可。设$P_{n}(A)$为第$ n $步到达$A $点的概率,那么由对称性可知:$P_{n}(A)+P_{n}(B)+P_{n}(C)+P_{n}(D)=1$
又知$A,B,C$三点完全等价,故有$P_{n}(A)=P_{n}(B)=P_{n}(C)=\frac{1-P_{n}(D)}{3}$
然后又可知第$ n-1 $步必定在$A,B,C$当中一点,且无论在哪一点总有$\frac{1}{3} $的概率走到$D$,故有:
$$P_{n+1}(D)=\frac{1}{3}(P_{n}(A)+P_{n}(B)+P_{n}(C))=\frac{1-P_{n}(D)}{3}$$
结合$P_{1}(D)=0$可算出$P_{n}(D)$的表达式为:$3^{n}P_{n}(D)=\frac{3}{4}(3^{n-1}-(-1)^{n-1})$
跟递推的通项公式相同。

打赏作者
3+

发表评论

电子邮件地址不会被公开。 必填项已用*标注