题解：CF226A Flying Saucer Segments

题解：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//万能头 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;//记得负数判断一下 }`