题解：CF226A Flying Saucer Segments

本蒟蒻的第一篇题解，请大家多多支持

思路

看到题的第一眼，想必大家都想到了 汉诺塔问题，可是当再次仔细查看此题，每一次只能移动到相邻的“柱子”，所以需要重新推导一遍通项。 先设人数为 $x$ 时，答案为 $f\left(x\right)$。 众所周知，汉诺塔的通项为 $f\left(x\right)=2^x-1$，那么此题的通项肯定与它相关。 怎么求呢？有两种方法。

$f1$: 递推大法

由题很容易可以得到 $f\left(x\right)=3\times f(x-1)+2$（因为在汉诺塔问题中，可以得到 $f\left(x\right)=2\times f(x-1)+1$，而此题中只能移动到相邻的飞船，也就是说系数和常数都应加一） 那么接下来就是化简。 由上文知： $$\text{[PARSE ERROR: Undefined("Command("textstyle")")]}f\left(x\right)+1=3\times \left(f\right(x-1)+1)$$ 那么： $$\text{[PARSE ERROR: Undefined("Command("textstyle")")]}\frac{f\left(x\right)+1}{f(x-1)+1}=3$$

又因为： $$\text{[PARSE ERROR: Undefined("Command("textstyle")")]}f\left(1\right)=2$$ 所以： $$\text{[PARSE ERROR: Undefined("Command("textstyle")")]}f\left(1\right)+1=3,f\left(2\right)+1=9,\text{[PARSE ERROR: Undefined("Command("dots")")]},f\left(x\right)+1=3^x$$ 则可以得到： $$\text{[PARSE ERROR: Undefined("Command("textstyle")")]}f\left(x\right)=3^x-1$$

$f2$: 找规律大法

回到汉诺塔问题，通项为 $f\left(x\right)=2^x-1$。 那么我们能否枚举本题中 $f\left(1\right),f\left(2\right),f\left(3\right),f\left(4\right)$ 的值并找到与 $f\left(x\right)=2^x-1$ 格式相近的通项呢？ 当然是可以的。 通过硬算大法和不断尝试，可以得到： $$\text{[PARSE ERROR: Undefined("Command("textstyle")")]}f\left(1\right)=2$$ $$\text{[PARSE ERROR: Undefined("Command("textstyle")")]}f\left(2\right)=8$$ $$\text{[PARSE ERROR: Undefined("Command("textstyle")")]}f\left(3\right)=26$$ $$\text{[PARSE ERROR: Undefined("Command("textstyle")")]}f\left(4\right)=80$$ 所以，我们可以“轻松”得到： $$\text{[PARSE ERROR: Undefined("Command("textstyle")")]}f\left(x\right)=3^x-1$$ 那么通过以上两种方法就可以得到我们所需要的通项了！！！

代码

#include//万能头
using namespace std;//命名空间
#define int long long//不开long long见祖宗
int n,m;
int mi(int x,int y){//快速幂
    int ans=1;
    while(y){
        if(y%2) ans*=x,ans%=m;
        y/=2,x=x*x%m;
    }
    return ans;
}
int32_t main(){    
    cin>>n>>m;
    cout

`#include//万能头
using namespace std;//命名空间
#define int long long//不开long long见祖宗
int n,m;
int mi(int x,int y){//快速幂
    int ans=1;
    while(y){
        if(y%2) ans*=x,ans%=m;
        y/=2,x=x*x%m;
    }
    return ans;
}
int32_t main(){    
    cin>>n>>m;
    coutmi(3,n)-1+m)%m;//记得负数判断一下
}`