题解：CF226A Flying Saucer Segments

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

思路

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

$f1$: 递推大法

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

又因为：
$$
\textstyle{f(1)=2}
$$
所以：
$$
\textstyle{f(1)+1=3,f(2)+1=9,\dots,f(x)+1=3^x}
$$
则可以得到：
$$
\textstyle{f(x)=3^x-1}
$$

$f2$: 找规律大法

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

代码

#include<bits/stdc++.h>//万能头
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<<(mi(3,n)-1+m)%m;//记得负数判断一下
}

#include<bits/stdc++.h>//万能头
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<<(mi(3,n)-1+m)%m;//记得负数判断一下
}