分析
一般汉诺塔的递推公式：$f[i]=2\times f[i-1]+1$。
猜想一波，在这道题的限制下，同样有$f[i]=k\times f[i-1]+b$。
先模拟出$f[1]$、$f[2]$和$f[3]$。
可以算出，$k=\frac{f[3]-f[2]}{f[2]-f[1]}$，$b=f[2]-k$。
然后就可以直接递推过去了。
代码
//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
typedef long long ll;
using namespace std;
inline int read() {
int X=0,w=1; char c=getchar();
while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
return X*w;
}
struct move { int u,v; } a[7];
int top[3],s[4][40];
ll f[40];
inline ll calc(int x) {
top[1]=top[2]=top[3]=0;
int ans=0,last=0;
for (re int i=x;i;--i) s[1][++top[1]]=i;
while (233) {
++ans;
for (re int i=1;i<=6;++i) {
int u=a[i].u,v=a[i].v;
if (!top[u]||s[u][top[u]]==last) continue;
if (top[v]&&s[u][top[u]]>s[v][top[v]]) continue;
last=s[v][++top[v]]=s[u][top[u]--];
break;
}
if (top[1]==x||top[2]==x||top[3]==x) return ans;
}
}
int main() {
int n=read();
for (re int i=1;i<=6;++i) {
char op[2]; scanf("%s",op);
a[i].u=op[0]-'A'+1,a[i].v=op[1]-'A'+1;
}
f[1]=calc(1),f[2]=calc(2),f[3]=calc(3);
int k=(f[3]-f[2])/(f[2]-f[1]),b=f[2]-k;
for (re int i=4;i<=n;++i) f[i]=f[i-1]*k+b;
printf("%lld\n",f[n]);
return 0;
}
打了一个小时表
wtcl
您怎么查我水表啊qwq
wtcl,不知道做什么题qwq
还有我们也要做bzoj前100qwq
$\texttt{_tham}$只要我们做HAOIqwq