Description

有 $ N $ 个人，标号为 $ i $,然后有三个位置，一开始所有人都在第一个位置，每一次每个人可以移动到相邻的位置，但需要满足他是他所处的位置与移动到的位置的最大数，问你所有人到第三个位置最少需要几次移动。

Method

本题提供两种思路，一种正经，一种不正经，建议看正经的。

打表找规律

首先我们可以看到题目中已经给了我们 $ 1 $ 和 $ 3 $ 的答案，那么我们可以考虑推出 $ 2 $ 时候的答案，可以知道 $ 2 $ 的时候答案为 $ 8 $ ,然后我们打开一个叫OEIS的网站，输入前三个答案，找到答案，发现答案为 $ 3^n-1 $ 然后快速幂即可。

真正挖掘性质

通过 $ 2 $ 与 $ 3 $ 的方案可知每一次，总是要从最大的开始把所有的数字移过去，那么我们考虑递推:

定义 $ f_i $ 为 有 $ i $ 个人时最少需要的移动次数，那么我们可以发现，每一次总是要先将 $ i-1 $ 个人移动到第三个位置，这次操作的代价为 $ f_{i-1} $ ,然后第二步将最小的那个 $ 1 $ 移到第二个位置，这是他唯一可以到的位置，然后再将 $ i-1 $ 个人移动到第一个位置，使 $ 1 $ 得以移动到第三个位置，最后再将这 $ i-1 $ 个人移到第三个位置，所以可以得到递推式 $ f_i=f_{i-1}*3+2 $ 。

做到现在，看到这个式子，你是不是已经认为到了终点，不，这个式子如果你直接做的话是要矩阵快速幂的，但是实际上我们观察这个式子，我们把它想象成三进制，那么每多一个人，就是相当于在这个三进制数后面多放了一个 $ 2 $ ,所以答案实际上就是 $ n $ 个 $ 2 $ 的三进制的十进制，就是 $ 3^n-1 $ ，还是回到了原来的式子。

Code

#include<bits/stdc++.h>
using namespace std;
long long n,MOD;
long long pow(long long x,long long y,long long p)
{
	long long ans=1;
	for (;y;y>>=1,x=x*x % MOD)
	   if (y&1) ans=ans*x % MOD;
	return ans;
}
int main()
{
	cin>>n>>MOD;
	n=pow(3,n,MOD);
	if (n==0) n=MOD-1;
	else n=n-1;
	cout<<n<<endl;
	return 0;
}

CF226A

原文：https://www.cnblogs.com/huangxuze/p/14674122.html